005 - 助けに来たぞ!!

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / x 9 /


TLE
1sec
MLE
64MB
得点
100

懺悔

問題文にて説明ができていないところがありましたので19年12月18日にて以下のことを追記します。大変失礼しました。

  • 塗装は昼に組み立てたパーツに行います。
  • 組み立て・塗装を終えたもののみ製品として扱います。
  • 昼に塗装、夜に組み立ては行えません。

問題

株式会社GBNではデーモンコアを作成しています。タコサシ支部では、昼の間にパーツ組み立てだけ行い、夜には塗装だけ行われます。塗装までして完成です。しかし全社員高熱で休むという異例な事態が発生しました。 それに焦った 工 場 長 のei1929は本社から応援猫の緊急派遣を要請し、見事n匹の猫が来てくれることになりました。しかし、応援に来てくれる猫は、応援に来れる猫であり、昼夜一方ならどちらでも働けるものの、仕事のスキルにムラがあります。 ei1929は考えることをやめているので、代わりにもっとも生産性の高いシフトを組んでください。 ちなみに、猫は少なくとも昼夜どちらかで働き、連続して働くことはできません。守ろう労基法!!

入力

 
n
a1  b1
a2  b2
…
an  bn
1行目に応援猫の数nが与えられます。 2行目からn+2行目にかけて、応援猫i(1≦i≦n)が昼に組み立てられる数ai と、夜に塗装できる数biが与えられます。

出力

もっとも生産できる組み合わせで、1日に生産できるデーモンコアの数を出力してください。

制約

 全ての入出力ケースについて以下を満たします。
  • 2 ≦ n ≦ 15
  • 0 ≦ ai,bi ≦ 500

入出力例

入力例1

3
2 6
7 2
4 1

出力例1

7
猫2が昼に組み立て、猫1,3が夜に塗装することで7個製造できます。

入力例2

2
10 3
4 9

出力例2

9

猫1が組み立て、猫2塗装をやった場合,10個組み立てられるものの,塗装は9個しかできないので、製造できるのは9個です。

入力例3

4
6 2
3 14
38 2
73 29

出力例3

43