1371: 作弊引擎
Description
该题输入量较大，请使用关闭同步流的 cin，或者使用 scanf，或者使用快读
题目背景
找到工作、无所事事的 $ajj$ 正在游玩 $《Cell$ $to$ $Singularity》$（细胞奇点）这是一个挂机类游戏，里面有一种资源，叫达尔文方块，这种资源可以购买几乎所有的其他资源，是一种高级通用货币，但是再生速度极其缓慢。你 $ajj$ 机智的想到可以使用 $Cheat$ $Engine$ （作弊引擎）来修改这种资源的数量，以获取这种只能通过充值来大量获取的资源。事实证明，他成功了，这个游戏并没有做反作弊检测。题目描述（题目背景和题目无关！）
$ajj$ 初始有 $0$ 个达尔文方块，经过多年的尝试， $ajj$ 掌握了 $n$ 种独特的作弊指令，第 $i$ 条指令的格式为三元组 $(a_i,b_i,c_i)$ ， $ajj$ 可以使用这些指令来获得达尔文方块，每种指令可以使用任意次。
第 $i$ 条指令可以让达尔文方块增加 $a_i$ 个。换句话说，如果在使用指令之前有 $k$ 个达尔文方块，使用指令之后就有 $k+a_i$ 个达尔文方块。
但是频繁使用作弊指令是要付出代价的， $ajj$ 被官方盯上了！这导致 $ajj$ 每天只能使用恰好一次作弊指令，而且如果 $ajj$ 在特定时间点使用特定的指令，那么官方就会扣除一定数量的达尔文方块（可以扣成负的）。具体的，如果第 $x$ 天使用的指令是第 $i$ 条，且 $x$ 是 $b_i$ 的倍数时（具体看样例解释）， $ajj$ 使用指令之后，会先扣除 $c_i$ 个达尔文方块，然后获得 $a_i $ 个。
规定 $ajj$ 开始使用指令的日子为第一天，记 $f(i)$ 表示经过了 $i$ 天之后 $ajj$ 手里达尔文方块的最大数量，$ajj$ 想让你计算 $$ \max^{m}_{i=1}f(i)\qquad(1\le m\le 10^9) $$
Input
第一行为 $t$（$1\le t \le 10^4$）。
接下来 $t$ 组数据。
每组的第一行为 $n,m$ ，描述指令的数量 $n$（$1\le n \le 5\times 10^5$） ，以及最大天数 $m$（$1\le m \le 10^9$） ，保证 $\sum n \le 5\times 10^5$ 。
之后输入 $n$ 个 $(a_i,b_i,c_i)$（$1\le a_i,b_i,c_i\le 10^9$） ，描述指令的具体内容。
Output
Sample Input Copy
6
1 1
3 3 3
1 7
4 2 5
2 4
1 2 4
2 2 5
5 8
12 1 11
10 1 4
1 1 3
1 2 5
2 1 7
1 1000000000
1000000000 4 987654321
1 10
2 2 3Sample Output Copy
3
13
2
48
753086419750000000
6HINT
第二组：第1~7天选择第1个指令（4-1+4-1+4-1+4=13）
第三组：第1天选择第2个指令（2），可以证明第1天是最优的
第四组：第1~8天选择第2个指令（6+6+6+6+6+6+6+6=48）
第五组：第1~1000000000天选择第1个指令（753086419750000000）
第六组：第1~9天选择第1个指令（2-1+2-1+2-1+2-1+2=6），可以证明第9天是最优的