33OJ
登录 注册

#ABC485F. 大桥

大桥

大桥

题目描述

有 NN 件物品 1,2,…,N1,2,\ldots,N,每件各一件。第 ii 件物品的价格为 cic_i,价值为 viv_i。

高桥每过一次桥,所有价格至少为 11 的物品的价格都会减少 11。

对每个 j=0,1,…,Mj=0,1,\ldots,M,求出下面这个值:在高桥过桥 jj 次之后,选出零件或多件物品,使得它们的总价格不超过 MM 时,所选物品总价值的最大值。

输入格式

输入第一行为两个整数 N,MN,M。

接下来 NN 行,第 ii 行为两个整数 ci,vic_i,v_i。

输出格式

输出 M+1M+1 行,共 M+1M+1 个整数。第 kk 行表示 j=k−1j=k-1 时的答案。

3 4
1 3
2 5
4 8
8
16
16
16
16

样例 1 解释

j=0j=0 时物品价格仍为初始价格,选择物品 1,21,2,总价值为 88。

j=1j=1 时所有物品价格减少 11,选择物品 1,2,31,2,3,总价格 0+1+3=40+1+3=4,总价值为 1616。

5 6
4 6
4 7
6 11
2 4
1 2
11
17
24
30
30
30
30
2 1
1 4
1 7
7
11

数据范围

对于所有测试数据,保证:

  • 1≤N≤1001 \le N \le 100;
  • 1≤ci≤M≤1041 \le c_i \le M \le 10^4;
  • 1≤vi≤1091 \le v_i \le 10^9;
  • 所有输入值均为整数。

子任务

本题共 20 个测试点,按测试点计分:

测试点 分值 每个测试点 特殊性质
1∼61 \sim 6 3030 55 N≤20N \le 20 且 M≤100M \le 100
7∼127 \sim 12 N≤100N \le 100 且 M≤2000M \le 2000
13∼2013 \sim 20 4040 无特殊限制

每个测试点单独评分,全部测试点的得分之和即为本题得分。