AT_yahoo_procon2018_qual_c 駆引取引

高桥君和青木君正在进行一场交易。一开始，高桥君的所持金为 $0$ 元。 高桥君拥有 $N$ 个编号为 $1$ 到 $N$ 的宝物。如果高桥君将第 $i$ 个宝物卖给青木君，可以获得 $x_i$ 元。 青木君出售 $N$ 个编号为 $1$ 到 $N$ 的商品。第 $i$ 个商品的价值为 $v_i$，售价为 $c_i$ 元。 交易按照以下步骤进行： 1. 高桥君可以选择出售宝物，或者购买商品。如果选择前者，则进入步骤 2；如果选择后者，则进入步骤 3。 2. 高桥君将自己持有的编号最小的宝物卖给青木君，获得相应金额。之后，青木君选择一个商品，停止其销售。然后返回步骤 1。 3. 高桥君可以购买当前在售的 $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 \leq 10^{15}$ - 所有输入均为整数 ### 样例解释 1 - 下面说明两个人的一种可能的行动顺序： 1. 高桥君选择出售宝物，卖出宝物 $1$，获得 $200$ 元。 2. 青木君停止销售商品 $2$。 3. 高桥君选择出售宝物，卖出宝物 $2$，获得 $1000$ 元。 4. 青木君停止销售商品 $3$。 5. 高桥君选择购买商品，买下商品 $1$，交易结束。 ### 样例解释 2 - 无论高桥君如何行动，都无法购买任何商品。 由 ChatGPT 4.1 翻译