解答：Submission #14704600 - AtCoder Beginner Contest 149
解法：「億マス計算」の類題。下記のブログを参考にしました。 tt-conpetitive.hatenablog.com
ひとまずAは昇順ソートする。
「M回の握手の幸福度の最大化」は「A[i] + A[j] (1 ≦ i, j ≦ N) のうち上位M個の和」と言い換えることができる。
{A[i] + A[j]} のうち上位M番目の数を求めるのは億マス計算同様にできる。すなわち和をxとしたときに「A[i] + A[j] ≧ xなる(i, j)がM個以下である」ような最小のxを二分探索で求めればよい。
ここで一工夫必要なのだが、上位M未満の数を求めておく（このときxは上位m < M番目であったとする）。これは「A[i] + A[j] ≧ xなる(i, j)がM個未満である」ような最小のxを二分探索で求める。
あとは、上位M個の和であるのだが、これを次の2つの足し算で求める。
①上位1～m番目の数の和
各iについて、A[i] + A[j] ≧ x であるA[j]を全て足せばよい。これは二分探索を使ってjを求めた後、A[j]～A[n]の和を累積和で求めればよい。
②m+1番目～M番目の数の和
実はこの数は全てx-1である。xがM番目未満となる最小の数であるので、x-1は必ずM番目より大きい数となる。また、xは上位m番目の数であることが分かっているので、m+1～M番目はxでないとつじつまが合わないためである。
よって(M - (m+1) - 1) * (x - 1)を足せばよい。
