問題文
1からまでの番号のついた匹の猫と1台のこたつがあります。番目の猫は最初は大きさですが、
こたつに入った猫は温まって溶けるため大きさが だけ大きくなります。()
つまり体の大きさがになります。
なるべく多くのねこちゃんたちをこたつにいれてあげたいですが、こたつは狭いので以下の条件を設けることにしました。
こたつに匹の猫が入り、その猫たちが十分に溶けた後
匹の猫の大きさの合計が匹の猫の大きさの合計以下になる。
上の条件を満たすような最大のを求めてください。
制約
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
...
...
出力
答えを出力せよ。
サンプル 1
入力
5
9 7 5 6 10
2 3 9 6 9
番目と 番目のねこちゃんをこたつにいれて十分に溶かすと、こたつに入ったねこちゃんたちの大きさは になります。
そのときこたつにいるねこちゃんの大きさの総和と、そうでないねこちゃんの大きさの総和は以下のようになります。
こたつにいる:
こたつにいない:
より、こたつに入るねこちゃんの数 は条件を満たします。
また、条件を満たしつつ より多くのねこちゃんをこたつに入れることはできないので、求める最大の は となります。
出力
2
サンプル 2
入力
4
9 7 9 8
0 4 0 2
出力
1
ログインして解答を提出
解答の提出や採点結果の確認には、ログインが必要です。
ログインする