AT_yahoo_procon2018_qual_c 駆引取引

[problemUrl]: https://atcoder.jp/contests/yahoo-procon2018-qual/tasks/yahoo_procon2018_qual_c 高橋君と青木君が取引をします。 はじめ、高橋君の所持金は $ 0 $ 円です。 高橋君は $ 1 $ から $ N $ の番号がついた $ N $ 個の財宝を持っています。高橋君は青木君に財宝 $ i $ を売却すると $ x_i $ 円得ることができます。 青木君は $ 1 $ から $ N $ の番号がついた $ N $ 個の商品を販売しています。商品 $ i $ は価値 $ v_i $ を持ち、価格 $ c_i $ 円で販売されています。 取引は以下の手順で行われます。 1. 高橋君は財宝を売却するか、商品を購入するかを決める。前者ならば手順 2. へ、後者ならば手順 3. へ進む。 2. 高橋君は持っている財宝のうち、最も番号が小さいものを青木君に売却しお金を得る。その後、青木君は商品を $ 1 $ つ選び販売を停止する。手順 1. へ戻る。 3. 高橋君は販売中の $ 0 $ 個以上の商品を購入し、取引を終了する。このとき、高橋君は所持金が $ 0 $ 円未満になるように購入することはできない。 高橋君が購入した商品の価値の総和を得点とします。 高橋君は得点を最大化するように、青木君は得点を最小化するように行動するとき、得点はいくつになりますか？

入力は以下の形式で標準入力から与えられる。 > $ N $ $ x_{1} $ $ ... $ $ x_{N} $ $ c_{1} $ $ ... $ $ c_{N} $ $ v_{1} $ $ ... $ $ v_{N} $

答えを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 18 $ - $ 1\ \leq\ x_i,c_i,v_i\leq10^{15} $ - 与えられる入力は全て整数 ### Sample Explanation 1 \- $ 2 $ 人の動きの一例について説明します。 1. 高橋君は財宝の売却を選び、財宝 $ 1 $ を売却し、$ 200 $ 円を得ます。 2. 青木君は商品 $ 2 $ の販売を停止します。 3. 高橋君は財宝の売却を選び、財宝 $ 2 $ を売却し、$ 1000 $ 円を得ます。 4. 青木君は商品 $ 3 $ の販売を停止します。 5. 高橋君は商品の購入を選び、商品 $ 1 $ を購入し、取引を終了します。 ### Sample Explanation 2 \- 高橋君がどのように行動しても、商品を購入することはできません。