cp-problems

しおり

問題文

Shuz* 君はしおりが挟まれている本を \(N\) 冊持っていて，\(i\) 番目の本は本 \(i\) と呼ばれます．各本 \(i\) には，表紙からの厚さが \(A_i\) の場所にしおりが挟まれています．しおりの厚さは \(0\) とします．また，各本 \(i\) の表紙から裏表紙までの厚さは \(B_i\) です．

⻑らくの間これらの本は放置されていたのですが，Shuz* 君はこれら \(N\) 冊の本を本棚に置き，表紙を左側にしてすきまなく一列に並べたいと思いました．Shuz* 君は見栄えがよくなるよう，\(N\) 冊の本を表紙を左側にしてすきまなく一列に並べたときに，以下に定義される醜さができるだけ小さくなるようにしたいと思っています．

• 隣り合っている \(2\) 冊の本に対し，左側の本のしおりから右側の本のしおりまでの厚さをしおり間距離とする．
• \(N\) 冊の本を表紙を左側にしてすきまなく一列に並べたとき，\(N - 1\) 個存在するしおり間距離のうち，最大のものをその並べ方の醜さとする．

\(N\) 冊の本を表紙を左側にしてすきまなく一列に並べたときの，醜さの最小値はどのくらいでしょうか．

制約

• \(1 \le N \le 18\)
• \(1 \le A_i \lt B_i \le 1000\)
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます．

入力
\(N\) \(A_1\, B_1\) \(A_2\, B_2\) \(\vdots\) \(A_N\, B_N\)

• \(1\) 行目に，Shuz* 君の持っている，しおりが挟まれている本の冊数 \(N\) が与えられます．
• 続く \(N\) 行に，\(1 + i\) 行目には \(A_i,\, B_i\) が半角スペース区切りで与えられます．

出力

\(N\) 冊の本を表紙を左側にしてすきまなく一列に並べたときの，醜さの最小値を出力してください．

最後に改行してください．

解説