在“迷你地铁”游戏的简化版中,只有一条地铁线路,所有火车都朝同一方向行驶。线路上有 $$$n$$$ 个车站,$$$a_i$$$ 人在游戏开始时在第 $$$i$$$ 个车站等候火车。游戏从第 $$$0$$$ 小时开始。每小时结束时(每小时结束前几分钟),$$$b_i$$$ 人会立即到达第 $$$i$$$ 个车站。如果在某个时刻,第$$$i$$$站的人数大于$$$c_i$$$,你就输了。
玩家有几趟列车,他可以指定几个小时。每趟列车的容量为 $$$k$$$ 乘客。 In the middle of the appointed hour, the train goes from the $$$1$$$-st to the $$$n$$$-th station, taking as many people at each station as it can accommodate.如果第 $$$i-1$$$-th 站有人,火车就不能从第 $$$i$$$-th 站载人。
如果在同一时间指定多趟列车,它们的运力将被累加并一起移动。
玩家希望在游戏中停留 $$$t$$$ 小时。确定他需要的最少火车数量。
输入
The first line contains three integers $$$n$$$, $$$t$$$, and $$$k$$$ ($$$1 \leq n, t \leq 200, 1 \leq k \leq 10^9$$$) — the number of stations on the line, hours we want to survive, and capacity of each train respectively.
Each of the next $$$n$$$ lines contains three integers $$$a_i$$$, $$$b_i$$$, and $$$c_i$$$ ($$$0 \leq a_i, b_i \leq c_i \leq 10^9$$$) — number of people at the $$$i$$$-th station in the beginning of the game, number of people每小时结束时到达第 $$$i$$$ 个车站以及第 $$$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
注意
让我们看一下示例。一共有三个站,第一站最初是2人,第二站是3人,第三站是4人。车站的最大容量分别为 10 个、9 个和 8 个。
制胜策略之一是在第一个小时和第三个小时指定两趟列车。 Then on the first hour, the train takes all of the people from the stations, and at the end of the hour, 4 people arrive at the first station, 3 on the second, and 2 on the third.
第二个小时没有指定的火车,最后,同样数量的人再次到达。
In the third hour, the train first takes 8 people from the first station, and when it arrives at the second station, it takes only 2 people because it can accommodate no more than 10 people.然后它经过第三站,因为它已经满了。之后,人们再次到达车站,游戏结束。
由于没有出现车站人数超过最大容量的时刻,所以我们使用两列火车获胜。