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.
n, t, k = map(int, input().split())
stations = []
for _ in range(n):
    a, b, c = map(int, input().split())
    stations.append((a, b, c))

trains_needed = 0
for hour in range(1, t + 1):
    for i in range(n):
        a, b, c = stations[i]
        people_waiting = a + b * hour
        if people_waiting > c:
            trains_needed += (people_waiting + k - 1) // k
            a = 0
        else:
            if i > 0:
                a -= min(a, k * (trains_needed - 1))
        stations[i] = (a, b, c)

print(trains_needed)