A11929 | 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.

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.

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