いったん \(\sum A_i\) 個の荷物をひとつずつ処理することを考えます．次の貪欲が正当です．

• 重い荷物から順に処理する．現時点で一番中身の軽い袋を選び，入れる．

簡単に証明の流れを書きます．

ある解に注目し，ある時点で次の状況を仮定します．

• 一番軽い袋 A
• 現在の解が，次の荷物を入れる袋を B
• 現時点で B の方が A より重いとする．

ここから先 A に入れる重量と B に入れる重量を比べて A の方が軽いならば，ここから先に追加する A, B の荷物を丸ごと入れ替えても，現在の解よりも悪くなりません．

ここから先 A に入れる重量が B にいま入れる重量 \(2^k\) 以上であるとします．特に A には \(2^k\) 以下の \(2\) べきを使って合計 \(2^k\) 以上を入れていることになります．

このとき，これらのある部分和がちょうど \(2^k\) になります（ここは証明が必要なところですが，省略します）．

これらの荷物を \(2^k\) の荷物と丸ごと入れ替えれも解が悪くなりません．このような交換によって，最適解であって次の荷物を A に入れるものがあると分かります．

以上の貪欲をシミュレートします．ただし荷物も袋もたくさんあるので適切にまとめます．

袋については，現時点での重量が同じものをまとめてグループ化して降順に並べておきます．

重さが一定荷物の荷物を処理していきます．まずは「末尾のグループに \(1\) 個ずつ入れる」ことが繰り返されます．この反復を \(O(1)\) 時間で行うようにします．この際どこかで，「末尾 \(2\) つのグループがまとまる」ということが起こりえます．これは，まとまる時点まででいったん反復を打ち切り，グループをまとめてから再開します．

最後に，荷物を末尾グループの途中まで \(1\) 個ずつ，残りは \(0\) 個ずつ入れるという形になります．

ある重さの荷物を処理する過程において，

• \(O(1)\) 時間かけて，グループ数が減る
• \(O(1)\) 時間かけて，グループ数が \(1\) つ増える（これはある重さの荷物について \(1\) 回以下）

が起こります．後者の回数は全体で \(O(M)\) 回，したがって前者の回数も全体で \(O(M)\) 回で，全体の計算量 \(O(M)\) 時間になります．

• 解答例：https://atcoder.jp/contests/arc226/submissions/77991289