No.54 Happy Hallowe'en

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 62
作問者 : なおなお
8 ProblemId : 41 / 出題時の順位表
問題文最終更新日: 2016-06-11 16:43:41

問題文

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

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

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

入力

\(N\)
\(V_1\ T_1\)
\(V_2\ T_2\)
\(\dots\)
\(V_i\ T_i\)
\(\dots\)
\(V_N\ T_N\)

\(1\)行目に、近所の家の数を表す整数\(N\ (1 \leq N \leq 10000)\)が与えられる。
続く\(N\)行に、\(i\)家\((1 \leq i \leq N)\)でもらえるおかしの数を表す整数\(V_i\ (1 \leq V_i \leq 10000)\)と、
おかしがもらえる閾値を表す整数\(T_i\ (1 \leq T_i \leq 10000)\) がスペース区切りで与えられる。

出力

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

サンプル

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。