No.710 チーム戦

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 63
作問者 : しらっ亭しらっ亭 / テスター : 37zigen37zigen
6 ProblemId : 2233 / 出題時の順位表

問題文

雪男くんと雪女さんの二人は、チームを組んで競技プログラミングのコンテストに出ることになりました。
コンテストに出るにあたり二人は必死に研鑽を積んで、

  • 問題文を一瞥した瞬間にそれぞれが問題を解くのに必要な秒数を正確に知る能力
  • あらゆる競技プログラミングの問題を $10^3$ 秒以内に正解する能力
を手に入れました。

さあコンテストが始まりました。
今回二人が参加するコンテストには問題が $N$ 問あります。
コンテストが始まった瞬間、$N$ 問の問題すべてを一瞥した雪男くんと雪女さんは、 各問題 $i$ について、雪男くんが解くのにかかる時間 $A_i$ (秒)と、雪女さんが解くのにかかる時間 $B_i$ (秒)を把握しました。

  • 二人は並列で問題を解いていきます
  • 一人の人が複数の問題を並列に解くことはしません
  • 一つの問題を二人が同時に解くことはしません
  • 二人とも、自分が担当する問題を順に、間隔を空けずに解いていきます
$N$ 問の問題を二人に適切に割り振り、全部の問題を解き終えるのに必要な最短の秒数を求めてください。

入力

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

$1 \le N \le 100$
$1 \le A_i, B_i \le 10^3$
入力は整数

出力

答えを1行で出力してください。

サンプル

サンプル1
入力
3
45 50
20 80
40 15
出力
60


問題1を雪女さん、問題2と3を雪男くんが担当すれば、60秒で全完です。

サンプル2
入力
5
600 100
700 100
800 100
900 100
1000 100
出力
500

雪男くんは座るだけでしたがチームは500秒で全完です。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。