公式の解説とちょっと違いそうなので

解説

まず、全部使うのが最適なのは明らかでいいでしょう(どうしても証明したい人は公式の解説の最初を読んでください。それはそうとなります)

最後に残るのを $r _ {1}, r _ {2}, \cdots , r _ {k}$ 、消すやつを $e _ {1}, e _ {2}, \cdots, e _ {n - k}$ としましょう。

$r _ {i}$ 内と $e _ {i}$ 内での順番を固定したとき、最大になるような並べ方は

$r _ {1}, r _ {2}, \cdots, r _ { k - 1}, e _ {1}, e _ {2}, \cdots , e _ {n - k} , r _{k}$

が最適です(こうでない場合こうすることで、損はしないことから示せます)

さて、あとは $r _ {i}$ と $e _ {i}$ 内での順番ですが、 $e _ {i}$ の順番は明らかに任意です。(常に $k - 1$ 個前にいるので)

$r _ {i}$ は $b _ {i}$ を掛ける数が単調増加していくことから、 $r _ {i}$ は $b _ {i}$ が非減少にならべるのが最適になります。

以上から、 $b _ {i}$ の値を非減少にソートして、dpをすれば解けました。

計算量は $O(Tnk)$ です。

提出コード

これ簡単だったのに、C2のせいでやらなかったのつらいなぁ…