問題文

高橋君と青木君が取引をします。 はじめ、高橋君の所持金は 0 円です。

高橋君は 1 から N の番号がついた N 個の財宝を持っています。高橋君は青木君に財宝 i を売却すると x_i 円得ることができます。

青木君は 1 から N の番号がついた N 個の商品を販売しています。商品 i は価値 v_i を持ち、価格 c_i 円で販売されています。

取引は以下の手順で行われます。

1. 高橋君は財宝を売却するか、商品を購入するかを決める。前者ならば手順 2. へ、後者ならば手順 3. へ進む。
2. 高橋君は持っている財宝のうち、最も番号が小さいものを青木君に売却しお金を得る。その後、青木君は商品を 1 つ選び販売を停止する。手順 1. へ戻る。
3. 高橋君は販売中の 0 個以上の商品を購入し、取引を終了する。このとき、高橋君は所持金が 0 円未満になるように購入することはできない。

高橋君が購入した商品の価値の総和を得点とします。

高橋君は得点を最大化するように、青木君は得点を最小化するように行動するとき、得点はいくつになりますか？

制約

• 1 \leq N \leq 18
• 1 \leq x_i,c_i,v_i\leq10^{15}
• 与えられる入力は全て整数

入力例 1

3
200 1000 1
100 100 300
1000 2000 1000000

出力例 1

1000

• 2 人の動きの一例について説明します。
  1. 高橋君は財宝の売却を選び、財宝 1 を売却し、200 円を得ます。
  2. 青木君は商品 2 の販売を停止します。
  3. 高橋君は財宝の売却を選び、財宝 2 を売却し、1000 円を得ます。
  4. 青木君は商品 3 の販売を停止します。
  5. 高橋君は商品の購入を選び、商品 1 を購入し、取引を終了します。

入力例 2

2
1 100
1 100
100 1

出力例 2

0

• 高橋君がどのように行動しても、商品を購入することはできません。

入力例 3

5
100 1 1 1 1
1 1 1 1 1
1000000000000000 1000000000000000 1000000000000000 1000000000000000 1000000000000000

出力例 3

4000000000000000

入力例 4

18
89 36 77 25 84 49 67 21 78 94 55 50 22 40 44 17 93 11
55 81 89 38 19 65 68 75 66 52 75 93 94 31 73 86 25 79
38 81 44 33 70 20 89 34 13 45 27 88 91 85 36 98 52 93

出力例 4

337