题目描述

​ 下北泽的某条铁道线路上设有 $n$ 个站点，从始发站到终点站分别编号为 $1,2,...,n$. 第 $i$ 号站点初始（第 $0$ 小时）有 $a_i$ 个人，在每个整小时的前几分钟会有 $b_i$ 人来到这个车站，如果在某个时刻这个车站的等车人数超过$c_i$人就会发生暴乱。

​ 为了防止暴乱的出现，你可以在开始后某个小时的中间时刻（即30分钟，1小时30分钟，2小时30分钟...）安排若干辆列车从始发站发往终点站，每辆列车的容量是 $k$，当列车到达某个站时，会尽可能多的搭载乘客，即列车如果搭载了第$x$个站的乘客那么之前站点都不会剩有等待的人。

​ 如果有若干辆列车同时发车，它们的容量可以看作是叠加的。

​ 你现在希望前 $t$ 个小时都不发生暴乱，最少需要安排多少辆列车？

输入格式

​ 第一行三个整数 $n,t,k$ ,表示站点个数，时间和列车容量。

​ 接下来 $n$ 行每行三个整数 $a_i,b_i,c_i$ , 描述一个站点。

输出格式

​ 一行一个整数，表示答案。

样例输入 1

3 3 10
2 4 10
3 3 9
4 2 8

样例输出 1

2

样例输入 2

4 10 5
1 1 1
1 0 1
0 5 8
2 7 100

样例输出 2

12

数据范围与提示

Subtask 1 (7 pts)

​ $n,t\le 5$

​ $k,a_i,b_i,c_i\le 10$

Subtask 2 (20 pts)

​ $a_i=0$

Subtask 3 (35 pts)

​ $n,t\le 50$

Subtask 4 (38 pts)

​ 无特殊限制

对于所有数据，$1\le n,t\le 200,1\le k\le 10^9,0\le a_i,b_i\le c_i\le10^9$