C - 居酒屋の最適メニュー選び 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は居酒屋に来ています。メニューには N 品の料理があり、i 番目の料理には「おいしさ」 A_i と「こってり度」 B_i が定められています。高橋君はこれらの料理の中から任意の組み合わせを選んで注文できます。各料理は最大 1 回まで注文でき、1 品も注文しないことも許されます（その場合、満足度は 0 です）。

高橋君はこってりした料理が好きですが、注文した料理のこってり度の合計が K を超えると、超過したこってり度 1 あたり満足度が D だけ下がってしまいます。

具体的には、高橋君の最終的な満足度は次の式で計算されます。

\text{満足度} = \left(\text{注文した料理のおいしさの合計}\right) - D \times \max\!\left(0,\ \text{注文した料理のこってり度の合計} - 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
  • 1 行目には、料理の数 N、こってり度の許容上限 K、超過 1 あたりの満足度減少量 D が、スペース区切りで与えられる。
  • 2 行目から N+1 行目には、各料理のおいしさとこってり度が与えられる。
  • 1+i 行目には、i 番目の料理のおいしさ A_i とこってり度 B_i がスペース区切りで与えられる。

出力

高橋君が得られる満足度の最大値を整数で 1 行に出力せよ。

入力例 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

Score : 366 pts

Problem Statement

Takahashi is at an izakaya (Japanese-style pub). The menu has N dishes, and the i-th dish has a "deliciousness" value A_i and a "richness" value B_i. Takahashi can order any combination of these dishes. Each dish can be ordered at most once, and it is also allowed to order no dishes at all (in which case, the satisfaction is 0).

Takahashi likes rich dishes, but if the total richness of the ordered dishes exceeds K, his satisfaction decreases by D for each unit of excess richness.

Specifically, Takahashi's final satisfaction is calculated by the following formula:

\text{Satisfaction} = \left(\text{Total deliciousness of ordered dishes}\right) - D \times \max\!\left(0,\ \text{Total richness of ordered dishes} - K\right)

Find the maximum satisfaction Takahashi can achieve.

Constraints

  • 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)
  • All inputs are integers

Input

N K D
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • The first line contains the number of dishes N, the richness tolerance limit K, and the satisfaction decrease per unit of excess D, separated by spaces.
  • From the 2nd line to the (N+1)-th line, the deliciousness and richness of each dish are given.
  • The (1+i)-th line contains the deliciousness A_i and richness B_i of the i-th dish, separated by a space.

Output

Print the maximum satisfaction Takahashi can achieve as an integer on a single line.

Sample Input 1

3 5 2
4 2
5 3
10 6

Sample Output 1

9

Sample Input 2

2 1 10
3 5
4 6

Sample Output 2

0

Sample Input 3

8 15 3
10 4
7 5
8 6
14 8
5 3
11 7
6 2
13 9

Sample Output 3

30

Sample Input 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

Sample Output 4

104

Sample Input 5

1 1 1000000
1000000 1000000

Sample Output 5

0