先生の身長を固定し、先生と児童の身長を昇順に並べ替えたものを \(h_0, h_1, \dots, h_N\) とします。
このとき、 \((h_0, h_1), (h_2, h_3), \dots, (h_{N-1}, h_N)\) でペアを作るのが最適です。

したがって、\(H\) をソートしておき、すべての変身形態 \(w\) について、 \(H\) の適切な位置に \(w\) を挿入して身長の差の合計を求めることで、 \(O(NM+N\log N)\) でこの問題を解くことができます。

しかし、このままでは TLE です。

回答例 (Python) : https://atcoder.jp/contests/abc181/submissions/17733459

そこで、 \(|H_{2i-1}-H_{2i}|\) の累積和 と \(|H_{2i}-H_{2i+1}|\) の累積和を持つと、挿入や合計に \(O(N)\) かける必要がなくなり、 \(O((N + M) \log N + M \log M)\) でこの問題を解くことができます。

回答例 (C++) : https://atcoder.jp/contests/abc181/submissions/17734513
回答例 (Python) : https://atcoder.jp/contests/abc181/submissions/17733390

また、 \(W\) をソートしておき、 \((H_{2i-1},H_{2i})\) でペアになる部分と \((H_{2i},H_{2i+1})\) でペアになる部分の境界と身長の差の合計を持って、しゃくとり法をしてもこの問題を解くことができます。

回答例 (Python) : https://atcoder.jp/contests/abc181/submissions/17733416