D - Selection of Gems Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は宝石店を経営しています。今度開催される宝石展示会に出品する宝石を選ぼうとしています。

店には N 種類の宝石があり、それぞれの宝石 i には価値 B_i と重さ W_i が設定されています。展示会場に持ち込める宝石の総重量には上限 C があり、それを超える重さの宝石を持ち込むことはできません。

高橋君は特殊な軽量化ケースを K 個持っています。この軽量化ケースを使うと、1個につき1種類の宝石の重さを半分（小数点以下切り捨て）にすることができます。ただし、同じ宝石に複数個のケースを使うことはできません。

高橋君は各種類の宝石を最大1つずつ持ち込むことができます。持ち込む宝石の価値の合計を最大化したいと考えています。

軽量化ケースを最適に使ったとき、持ち込むことができる宝石の価値の合計の最大値を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq C \leq 10^5
  • 0 \leq K \leq \min(N, 30)
  • N(K+1)(C+1) \leq 2 \times 10^7
  • 1 \leq B_i \leq 10^9
  • 1 \leq W_i \leq 2C
  • 入力はすべて整数である

入力

N C K
B_1 W_1
B_2 W_2
:
B_N W_N
  • 1 行目には、宝石の種類数を表す N 、重量の上限を表す C 、軽量化ケースの個数を表す K が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各宝石の情報が与えられる。
  • 1 + i 行目では、宝石 i の価値 B_i と重さ W_i が、スペース区切りで与えられる。

出力

持ち込むことができる宝石の価値の合計の最大値を 1 行で出力してください。

入力例 1

4 10 1
8 6
10 7
5 4
6 5

出力例 1

18

入力例 2

5 12 0
7 3
12 8
9 5
4 6
11 10

出力例 2

19

入力例 3

12 50 3
30 18
45 27
25 15
60 40
35 22
50 35
20 12
55 45
40 30
15 10
70 55
28 16

出力例 3

155

入力例 4

40 300 6
120 80
250 180
90 60
310 240
180 130
400 350
75 45
220 170
500 420
160 110
330 260
140 90
270 200
600 500
95 70
210 160
450 380
125 85
360 290
280 210
510 460
170 125
390 310
240 190
700 590
155 100
430 330
105 75
320 250
260 205
540 440
190 140
470 360
115 95
350 270
290 230
620 520
200 150
410 340
130 105

出力例 4

885

入力例 5

1 1 1
1000000000 2

出力例 5

1000000000

Score : 400 pts

Problem Statement

Takahashi runs a jewelry store. He is trying to select jewels to exhibit at an upcoming jewelry exhibition.

The store has N types of jewels, and each jewel i has a value B_i and a weight W_i. There is an upper limit C on the total weight of jewels that can be brought to the exhibition venue, and jewels exceeding this weight cannot be brought in.

Takahashi has K special weight-reduction cases. By using one weight-reduction case, he can halve the weight of one type of jewel (rounded down to the nearest integer). However, multiple cases cannot be used on the same jewel.

Takahashi can bring at most one jewel of each type. He wants to maximize the total value of the jewels he brings.

Find the maximum total value of jewels that can be brought when the weight-reduction cases are used optimally.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq C \leq 10^5
  • 0 \leq K \leq \min(N, 30)
  • N(K+1)(C+1) \leq 2 \times 10^7
  • 1 \leq B_i \leq 10^9
  • 1 \leq W_i \leq 2C
  • All inputs are integers

Input

N C K
B_1 W_1
B_2 W_2
:
B_N W_N
  • The first line contains N representing the number of types of jewels, C representing the weight limit, and K representing the number of weight-reduction cases, separated by spaces.
  • From the 2nd line to the (N + 1)-th line, the information of each jewel is given.
  • The (1 + i)-th line contains the value B_i and weight W_i of jewel i, separated by spaces.

Output

Print the maximum total value of jewels that can be brought in a single line.

Sample Input 1

4 10 1
8 6
10 7
5 4
6 5

Sample Output 1

18

Sample Input 2

5 12 0
7 3
12 8
9 5
4 6
11 10

Sample Output 2

19

Sample Input 3

12 50 3
30 18
45 27
25 15
60 40
35 22
50 35
20 12
55 45
40 30
15 10
70 55
28 16

Sample Output 3

155

Sample Input 4

40 300 6
120 80
250 180
90 60
310 240
180 130
400 350
75 45
220 170
500 420
160 110
330 260
140 90
270 200
600 500
95 70
210 160
450 380
125 85
360 290
280 210
510 460
170 125
390 310
240 190
700 590
155 100
430 330
105 75
320 250
260 205
540 440
190 140
470 360
115 95
350 270
290 230
620 520
200 150
410 340
130 105

Sample Output 4

885

Sample Input 5

1 1 1
1000000000 2

Sample Output 5

1000000000