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 = 211

content1 = input().split()
n = int(content1[0])
k = int(content1[2])
t = int(content1[1])

a = [0]*N
b = [0]*N
c = [0]*N
sa = [0]*N
sb = [0]*N
sc = [0]*N

d=[[[0] * N for i in range(N)] for j in range(2)]
g=[[[0] * N for i in range(N)] for j in range(2)]

for i in range(1,n+1):
    content = input().split()
    a[i]=(int(content[0]))
    b[i]=(int(content[1]))
    c[i]=(int(content[2]))

n=n+1
a[n]=2e18
b[n]=0
c[n]=2e18

for i in range(1,n+1):
    sa[i] = sa[i - 1] + a[i]
    sb[i] = sb[i - 1] + b[i]
    sc[i] = sc[i - 1] + c[i]

for p in range(1,n+1):
    for s in range(0,n+1):
        for z in range(0,2):
            d[p][s][z] = 2e18
            g[p][s][z] = 2e18
            if d[p-1][s][z]<2e18 and a[p]*z+b[p]*s<=c[p]:
                d[p][s][z] = d[p - 1][s][z]
                d = (z * sa[p-1]+s * sb[p-1]+k-1) / k
                if d * k <= z * sa[p]+s * sb[p]:
                    g[p][s][z] = d

            for r in range(s):
                if g[p][r][z]<2e18:
                    m = z * sa[p] + r * sb[p] - k*g[p][r][z]
                    x = (max(m + (s - r) * b[p] - c[p], 0) + k - 1) / k
                    m -= x * k
                    if m >= 0 and d[p-1][s-r][0] < 2e18:
                        d[p][s][z]=min(d[p][s][z], g[p][r][z]+x+d[p-1][s-r][0])
                        d=((s-r) * sb[p-1]+k-1) / k
                        if d * k <= m+(s-r) * sb[p]:
                            g[p][s][z]=min(g[p][s][z], g[p][r][z]+x+d);

print(d[n][t][1])

