← 返回题目列表

AtCoder · yahoo_procon2018_qual_c

C. 駆引取引

中文机器翻译题面 查看原题

配点 : 500 点

問題文

高桥君和青木君进行交易。 一开始,高桥君拥有的现金是 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}
  • 给出的所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

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. 高桥君选择出售财宝,出售 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