分数: 366 分
问题陈述
高桥在居酒屋(日式酒吧)。菜单有 N 菜肴,以及 i第道菜有“美味”值 A_i 和“丰富”值 B_i。高桥可以点这些菜肴的任意组合。每道菜最多只能点一次,也可以不点菜(此时满意度为 0).
高桥喜欢丰富的菜肴,但如果点的菜品的总丰富度超过 K,他的满意度降低了 D 每个单位的过度丰富度。
具体来说,高桥的最终满意度通过以下公式计算:
\text{Satisfaction} = \left(\text{Total deliciousness of ordered dishes}\right) - D \times \max\!\left(0,\ \text{Total richness of ordered dishes} - K\right)
找出高桥可以达到的最大满意度。
约束
- 1 \leq N \leq 19
- 1 \leq K \leq 10^6
- 1 \leq D \leq 10^6
- 1 \leq A_i \leq 10^6 (1 \leq i \leq N)
- 1 \leq B_i \leq 10^6 (1 \leq i \leq N)
- 所有输入均为整数
输入
N K D A_1 B_1 A_2 B_2 \vdots A_N B_N
- 第一行包含菜品数量 N,丰富度容差极限 K,每超出一个单位满意度就会降低 D,以空格分隔。
- 从第 2 行到 (N+1)第3行,给出了每道菜的美味和丰富。
- 的 (1+i)第行包含美味 A_i 和丰富性 B_i 的 i第一个菜,以空格分隔。
输出
在一行上以整数形式打印高桥所能达到的最大满意度。
示例输入 1
3 5 2 4 2 5 3 10 6
示例输出 1
9
示例输入 2
2 1 10 3 5 4 6
示例输出 2
0
示例输入 3
8 15 3 10 4 7 5 8 6 14 8 5 3 11 7 6 2 13 9
示例输出 3
30
示例输入 4
19 50 4 12 5 7 4 20 10 18 9 5 2 11 6 9 5 14 7 6 3 25 13 8 4 16 8 10 6 13 7 21 11 4 1 17 9 15 8 19 10
示例输出 4
104
示例输入 5
1 1 1000000 1000000 1000000
示例输出 5
0