时间限制： 500ms

空间限制： 64MB

鲨鲨有 $p$ 个 $0$ 号空瓶子。

有 $N$ 个商店，在第 $i$ 个商店可以用 $A_i$ 个空瓶子（$0$ 号瓶子或者 $i$ 号瓶子）换取 $B_i$ 个装满果汁的 $i$ 号瓶子。保证 $A_i \gt B_i$。

鲨鲨每喝掉一瓶装在 $i$ 号瓶子里的果汁，就会获得 $C_i$ 的精神值。

请对于 $p \in \{1, 2, \dots, M\}$，分别求出鲨鲨可以获得的最大精神值。

输入格式

第一行两个整数 $N, M$。

接下来 $N$ 行，每行三个整数 $A_i, B_i, C_i$。

输出格式

对于 $p \in \{1, 2, \dots, M\}$，各输出一行，一个整数表示答案。

样例 1

输入

2 5
4 3 3
5 2 8

输出

0
0
0
9
18

样例 2

见下发文件bottle2.in/out.

数据范围

对于 $20\%$ 的数据，$N = 1$ 。

对于 $100\%$ 的数据，$1 \le N \le 5000,2 \le M \le 5000,1 \le B_i \lt A_i \le M,1 \le C_i \le 10^9$ 。