008 - 助けに来たぞ！！

懺悔

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

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

問題

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

入力

　

n
a1  b1
a2  b2
…
an  bn

１行目に応援猫の数nが与えられます。 ２行目からn+2行目にかけて、応援猫i(1≦i≦n)が昼に組み立てられる数a_i と、夜に塗装できる数b_iが与えられます。

出力

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

制約

　全ての入出力ケースについて以下を満たします。

• 2　≦ n ≦　15
• 0　≦ a_i,b_i ≦　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