\(\{ A_i + A_j \}\) の上位 \(M\) 個の合計を求める問題である. しかし, まともにやると時間計算量も空間計算量も制限を超えてしまうのでどうするか.

まずは \(\{ A_i \}\) は降順にソートしておく.

次に \(A_i + A_j \geq X\) となる握手を行ったときの握手の回数を \(S(X)\) とする. これは \(i\) が決まれば \(j\) の個数は二分探索で求めることができるので, すべての \(i\) について \(j\) の個数を求めて合計する. 同時に幸福度 \(H(X)\) も累積和を使って計算する.

\(S(x) \leq M\) を満たす最小の \(x\) を二分探索で求め, 同時に \(S(y) \lt M\) を満たす最大の \(y\) を求める. このとき, 残りの \(M-S(x)\) 回の握手は幸福度 \(y\) の握手を行うことになる.

これを合わせると, 最大の幸福度は \(H(x) + (M-S(x)) y\) となる.