#713 新都市建設

問題文

問題文の言語

$N$ 棟の建物を設計します。建物 $i$ は最大 $A_i$ 階まで建てることができます。

建物の高さが $h$ 階のとき、都市の完成度は $B_h$ 増加します。都市の完成度の初期値は $0$ であり、各建物の高さは正の整数でなければなりません。

都市の完成度の最大値を求めてください。

入力は以下の形式で標準入力から与えられます。

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

各テストケースについて、都市の完成度の最大値を $1$ 行に出力してください。

#	得点	制約
1	32	$N \leq 1000$ . $M \leq 1000$ . すべてのテストケースにおける $N+M$ の総和は以下である。

入力例

出力例

14
15

最初のテストケースでは、各建物の高さを順に $1,1,3,3,5$ 階とします。各建物の寄与は $2,2,3,3,4$ なので、完成度は $2 + 2$ となり、これが最大値です。