该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

$xyx$是$N$城码头的一位装箱工，他每天的工作就是将运达码头的货物装入集装箱中，以便后续运输。受码头集装箱的运输效率限制，$xyx$身边并不总有足够的集装箱以供装货。具体地，码头集装箱运输条例规定，初始时刻（即$t = 0$时）$xyx$身边有一个集装箱，此后每间隔$T$个单位时间，一个新的集装箱就会被送抵码头以供$xyx$使用（例如，$t = T$ 时，$xyx$身边有两个集装箱）。

为了规范装货，集装箱的容量均为$W$ 。

现有$n$种货物依次抵达码头，其中第$i$种货物的到达时间为$t_i$，共有$w_i$件，每件货物的价值为$v_i$，且每件的体积均为1。显然，因为货物到达时刻可使用集装箱的剩余容积可能不够，$xyx$并不总能将每种货物都直接全部装入集装箱。

对此，摸鱼的他的策略如下：当第$i$种货物到达时，假设此时码头可用集装箱的所有空余体积之和为$W_0$；若$w_i ⩽ W_0$，则将该种货物全部装入；否则，仅装入$W_0$件第$i$种货物，并直接将第$i$种货物剩余的部分全部抛弃。

$xyx$想知道，当全部$n$种货物都运抵码头，自己装箱完成后，所有集装箱内装入货物的价值之和为多少？

（注：若货物和新集装箱在同一时刻到达，则$xyx$在装该种货物的时候，已经可以使用新集装箱。）

输入格式

第一行三个整数$n$, $T$, $W$,其含义见题目描述；

接下来共$n$行，每行三个整数$t_i, w_i, v_i$，表示第$i$种货物抵达码头时间、数量和单件价值；

输出格式

共一行，一个整数，表示全部货物装箱完成后，所有集装箱内装入货物的价值之和。

样例

3 3 3
1 2 1
2 2 2
3 3 1

7

数据范围

本题共有10个测试点。

对于$50\%$的数据，满足 $n = 1,t_1 = 1$

对于另外$30\%$的数据，$1 ⩽ n ⩽ 10$

对于$100\%$的数据：

$1 ⩽ n, T ⩽ 10^5，1 ⩽W⩽ 10^6$

$1 ⩽ t_i, w_i, v_i ⩽ 10^6$

对于任意$1 ⩽ i < j ⩽ n$，有$t_i< t_j$