8342: 大航海时代
[Creator : ]
Description
小明打算从 A 地运若干货物到 B 地卖掉。岛上有 n 个货物，第 i 个货物的重量是 $w_i$ 千克、如果运到 B 第变卖可以获得 $v_i$ 个金币。
小明打算用一艘船运走这些货物，为了航海的稳定性、船的总重量不能多也不能少、不足的部分、小明需要另外购买配重补足。 具体地说、船上的装的所有货物和配重的总重量必须恰好等于 m。每千克配重的售价等于 k 个金币。
小明在 n个货物中选择若干个购买装船、并且购买配重使得装船货物和配重总重恰好等于 m，运输到B地后将所有货物变卖，卖得的金币减去购买配重花掉的金币就是他的获利。那么他最多可以获利多少个金币？
注意不论如何选择货物，船一定要出航，小明必须购买配重。所以小明有可能亏损，此时只能寻找一个亏损最少的方案。答案可能是负数。
Input
第 1 行，3 个正整数 n,m,k
接下来 n 行，每行 3 个正整数 $w_i,v_i$
Output
输出一个整数，表示最多可以获利的金币数量。
Constraints
100% 数据：
$1≤n≤5\times 10^2,\ 1≤w_i,v_i≤10^3,\ 1≤m≤5\times 10^4,\ 1≤k≤10$
Sample 1 Input
3 6 2
2 5
6 1
1 3
Sample 1 Output
2
选择第 1,3 个货物总重量 3 千克，再购买 3 千克配重，花费 6 个金币。
卖出后可以获得 8 个金币。总获利 2 个金币。
卖出后可以获得 8 个金币。总获利 2 个金币。
Sample 2 Input
3 6 10
2 5
5 1
2 3
Sample 2 Output
-9
选择第 2 个货物，总重量 5 千克，再购买 1 千克配重，花费 10 个金币。
可以获得 1 个金币。总获利 -9 个金币。
这是亏损最少的方法。
可以获得 1 个金币。总获利 -9 个金币。
这是亏损最少的方法。
Sample 3 Input
10 133 3
12 16
14 41
19 3
20 34
29 25
29 19
30 26
2 5
17 8
47 31
Sample 3 Output
140