← 返回题目列表

AtCoder · awc0109_d

D. 宝石的选择

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

分数: 400 分

问题陈述

高桥经营一家珠宝店。他正在尝试选择珠宝在即将举行的珠宝展览会上展出。

商店有 N 珠宝的类型以及每种珠宝 i 有一个值 B_i 和一个重量 W_i。有上限 C 可带入展览场馆的珠宝首饰总重量,超过此重量的珠宝首饰不能带入。

高桥有 K 特殊减肥案例。通过使用一个减重盒,他可以将一种宝石的重量减半(四舍五入到最接近的整数)。但是,同一件珠宝不能使用多个盒子。

高桥每种类型最多可以携带一颗宝石。他希望最大化他所带来的珠宝的总价值。

求最佳使用减重箱时可以带来的最大珠宝总价值。

约束

  • 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
  • 第一行包含 N 代表珠宝的种类数量, C 代表重量限制,以及 K 代表减重案例的数量,以空格分隔。
  • 从第 2 行到 (N + 1)第行,给出了每颗宝石的信息。
  • 的 (1 + i)- 第行包含值 B_i 和重量 W_i 的宝石 i,用空格分隔。

输出

打印一行中可以携带的珠宝的最大总价值。


示例输入 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