10976: 小落买卖
[Creator : ]
Description
小落在玩一款模拟经营游戏，这个游戏按时间排序有 $n$ 个事件，每个事件可以在两种选项中选择一种:
(1) 消耗 $x$ 颗宝石，获得 $y$ 枚金币。
(2) 获得 $z$ 颗宝石。
不过，宝石的数量是有上限的，在任何时刻，若小落的宝石数量大于 $m$，则大于 $m$ 部分的宝石直接消失。
$n$ 个事件结束后，除了现有金币，每剩余一颗宝石可兑换一枚金币。
(1) 消耗 $x$ 颗宝石，获得 $y$ 枚金币。
(2) 获得 $z$ 颗宝石。
不过，宝石的数量是有上限的，在任何时刻，若小落的宝石数量大于 $m$，则大于 $m$ 部分的宝石直接消失。
$n$ 个事件结束后，除了现有金币，每剩余一颗宝石可兑换一枚金币。
Input
第一行输入两个整数 $n, m\ (1≤n,m≤1000)$ 表示事件个数和宝石上限。
接下来 $n$ 行，每行输入三个整数 $x, y, z\ (1≤x,y,z≤10^9)$ 表示每一个事件
接下来 $n$ 行，每行输入三个整数 $x, y, z\ (1≤x,y,z≤10^9)$ 表示每一个事件
Output
输出一个整数表示 $n$ 个事件结束后的最大金币数量。
Sample 1 Input
3 3
1 2 1
1 3 1
1 2 1
Sample 1 Output
4
Sample 2 Input
4 15
1 4 10
1 10 1
8 1 4
3 10 9
Sample 2 Output
30
Sample 3 Input
5 1000
31049 12574 18520
25260 24339 1380
1747 4243 18333
27218 7334 8316
17910 32327 26632
Sample 3 Output
0
10 1000
225 9270 20
130 29536 81
432 20889 60
20 9486 34
137 16777 22
304 9855 36
442 28882 55
21 28569 61
258 26812 66
225 14296 13
55423