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