CF1007E.Mini Metro

In a simplified version of a "Mini Metro" game, there is only one subway line, and all the trains go in the same direction. There are $n$ stations on the line, $a_i$ people are waiting for the train at the $i$-th station at the beginning of the game. The game starts at the beginning of the $0$-th hour. At the end of each hour (couple minutes before the end of the hour), $b_i$ people instantly arrive to the $i$-th station. If at some moment, the number of people at the $i$-th station is larger than $c_i$, you lose.

A player has several trains which he can appoint to some hours. The capacity of each train is $k$ passengers. 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. A train can not take people from the $i$-th station if there are people at the $i-1$-th station.

If multiple trains are appointed to the same hour, their capacities are being added up and they are moving together.

The player wants to stay in the game for $t$ hours. Determine the minimum number of trains he will need for it.

在“迷你地铁”（Mini Metro）游戏的一个简化版本中，仅有一条地铁线路，且所有列车均朝同一方向行驶。该线路上共有 $n$ 个车站，游戏开始时（即第 $0$ 小时初），第 $i$ 个车站有 $a_i$ 名乘客正在等待列车。游戏从第 $0$ 小时初开始。每小时结束时（即在该小时即将结束前的几分钟），第 $i$ 个车站会瞬间新增 $b_i$ 名乘客。若在任意时刻，第 $i$ 个车站的乘客数量超过 $c_i$，则游戏失败。

玩家拥有若干列列车，可将它们指派至特定的小时。每列列车的载客容量为 $k$ 人。在被指派的小时的正中时刻，列车将从第 $1$ 个车站出发，依次驶向第 $n$ 个车站；在每个车站，列车尽可能多地搭载乘客（但不超过其剩余容量）。若第 $i-1$ 个车站仍有乘客未被接走，则列车不能在第 $i$ 个车站上客。

若多列列车被指派至同一小时，则它们的容量相加，并一同运行。

玩家希望游戏持续至少 $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 arriving to $i$-th station in the end of each hour and maximum number of people at the $i$-th station allowed respectively.

第一行包含三个整数 $n$、$t$ 和 $k$（$1 \leq n, t \leq 200$，$1 \leq k \leq 10^9$），分别表示线路中的车站数量、希望存活的小时数以及每列火车的容量。

接下来的 $n$ 行中，每行包含三个整数 $a_i$、$b_i$ 和 $c_i$（$0 \leq a_i, b_i \leq c_i \leq 10^9$），分别表示游戏开始时第 $i$ 个车站的人数、每小时结束时到达第 $i$ 个车站的人数，以及第 $i$ 个车站允许容纳的最大人数。

Output a single integer number — the answer to the problem.

输出一个整数——该问题的答案。

Let's look at the sample. There are three stations, on the first, there are initially 2 people, 3 people on the second, and 4 people on the third. Maximal capacities of the stations are 10, 9, and 8 respectively.

One of the winning strategies is to appoint two trains to the first and the third hours. 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 second hour there are no trains appointed, and at the end of it, the same amount of people are arriving again.

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. Then it passes by the third station because it is already full. After it, people arrive at the stations once more, and the game ends.

As there was no such moment when the number of people at a station exceeded maximal capacity, we won using two trains.

我们来看这个样例。共有三个车站：第一个车站初始有 2 人，第二个车站有 3 人，第三个车站有 4 人。各车站的最大容量分别为 10、9 和 8。

其中一种获胜策略是：在第一小时和第三小时各安排一列火车。
在第一小时，该列车将所有车站的乘客全部接走；该小时结束时，第一个车站新到达 4 人，第二个车站到达 3 人，第三个车站到达 2 人。

第二小时不安排列车，该小时结束时，各车站同样分别新到达 4 人、3 人和 2 人。

第三小时，列车首先从第一个车站接走 8 人；当它抵达第二个车站时，仅能再接走 2 人（因为列车总载客量上限为 10 人）；随后它经过第三个车站而不停车（此时列车已满员）。此后，各车站再次迎来新乘客，游戏结束。

由于在整个过程中，任一车站的乘客数量均未超过其最大容量，因此我们仅用两列火车便取得了胜利。