← 返回题目列表

AtCoder · awc0062_c

C. 居酒屋的最佳菜单选择

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

分数: 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