問題一覧 > 通常問題

No.54 Happy Hallowe'en

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 106
作問者 : なおなお
13 ProblemId : 41 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-06-11 16:43:41

問題文

今日はハロウィンなので、太郎君は近所の家におかしをもらいに行くことにしました。

近所には、太郎君の家以外に N軒の家があります。
それぞれのi家に行くとおかしをVi個もらえるのですが、
近所のこどもたちに平等におかしを配るため、
すでにおかしをTi個以上持っていると、おかしを一つももらえないことになっています。

太郎君は、最初におかしを一つも持っていないこととし、近所の家を周るのは好きな順番で周ることができるとき、
太郎君がもらえるおかしの最大の個数を求めてください。
同じ家には1回しか回れないとします。

入力

N
V1 T1
V2 T2

Vi Ti

VN TN

1行目に、近所の家の数を表す整数N (1N10000)が与えられる。
続くN行に、i(1iN)でもらえるおかしの数を表す整数Vi (1Vi10000)と、
おかしがもらえる閾値を表す整数Ti (1Ti10000) がスペース区切りで与えられる。

出力

太郎君がもらえるおかしの最大の個数を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3
1 1
3 2
5 3
出力
6

1軒目に行くと、所持おかし数が0個なので1個もらえます。
次に2軒目に行くと、所持おかし数が1個なので3個もらえますが、
それよりも、3軒目に行くと5個もらえるので、最大で1+5=6個もらえます。

サンプル2
入力
5
1 1
1 4
1 2
1 5
1 3
出力
5

すべての家を適切な順で周ることで最大5個のおかしがもらえます。

サンプル3
入力
7
2 1
2 3
9 2
3 1
6 4
3 5
4 8
出力
11

1,2,6,7軒目の家の順に行き、おかしを2,2,3,4個の順にもらいます。

サンプル4
入力
2
1 3
100 2
出力
101

sugimさんより提供頂きました。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。