配点 : 500 点
問題文
高桥君和青木君进行交易。 一开始,高桥君拥有的现金是 0 这是日元。
高桥君 1 减去 N 有 N 拥有个宝物。高桥君如果向青木君出售宝物 i 可以获得 x_i 日元。
青木先生 我们正在调查 1 减去 N 有 N 销售了个商品。商品 i 是一个值 当我收到价值低于 v_i 持有,售价为 c_i 日元。
交易按照以下步骤进行。
- 高桥君决定是出售宝物还是购买商品。如果是前者,则进行步骤 2,如果是后者,则进行步骤 3。
- 高桥君会将手中编号最小的宝物卖给青木君并获得金钱。之后,青木君将商品 1 选择停止销售。步骤 1. 返回。
- 高桥君正在销售中的 0 件以上的商品并完成交易。在此时,高桥君不能购买以致于持有资金少于 0 日元。
高桥君购买商品的总价值作为得分。
当高桥君为了最大化得分行动,而青木君为了最小化得分行动时,得分是多少?
制約
- 1 \leq N \leq 18
- 1 \leq x_i,c_i,v_i\leq10^{15}
- 给出的所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N
x_{1} ... x_{N}
c_{1} ... c_{N}
v_{1} ... v_{N}
出力
打印答案。 来自
入力例 1
3 200 1000 1 100 100 300 1000 2000 1000000
出力例 1
1000
- 2 说明一种人的行动示例。
- 高桥君选择出售财宝,出售 1 的财宝,200 日元收入。
- 青木君停止销售商品 2 。
- 高桥君选择出售财宝,出售 2 的财宝,1000 日元收入。
- 青木君停止销售商品 3 。
- 高桥君选择购买商品,购买 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