Problem: 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.

Input

The first line contains three integers n, t, and k (1 ≤ n, t ≤ 200, 1 ≤ k ≤ 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 ≤ a_i, b_i ≤ c_i ≤ 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

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

Examples

Input

3 3 10
2 4 10
3 3 9
4 2 8


Output

2


Input

4 10 5
1 1 1
1 0 1
0 5 8
2 7 100


Output

12

Note

<image>

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.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
namespace fastExpress {
template <typename T>
inline T read() {
  T f = 1, x = 0;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * f;
}
template <typename T>
inline void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
inline void print_char(T x, char ch) {
  write(x), putchar(ch);
}
template <typename T>
inline void char_print(char ch, T x) {
  putchar(ch);
  write(x);
}
template <typename T>
inline void print_space(T x) {
  print_char(x, ' ');
}
template <typename T>
inline void space_print(T x) {
  char_print(' ', x);
}
template <typename T>
inline void println(T x) {
  print_char(x, '\n');
}
template <typename T>
inline void lnprint(T x) {
  char_print('\n', x);
}
template <typename T>
inline void print_array_in_range1(T* a, int l, int r) {
  for (int(i) = (l); (i) <= (r); ++(i)) print_char(a[i], " \n"[i == r]);
}
template <typename T>
inline void print_array_in_range2(T* a, int l, int r) {
  println(r - l + 1), print_array_in_range1(a, l, r);
}
template <typename T>
inline void print_array_in_range3(T* a, int l, int r) {
  for (int(i) = (r); (i) >= (l); --(i)) print_char(a[i], " \n"[i == l]);
}
template <typename T>
inline void print_array_in_range4(T* a, int l, int r) {
  println(r - l + 1), print_array_in_range3(a, l, r);
}
template <typename T>
inline void print_array_in_range5(T* a, int l, int r) {
  for (int(i) = (l); (i) <= (r); ++(i)) println(a[i]);
}
template <typename T>
inline void print_array_in_range6(T* a, int l, int r) {
  println(r - l + 1), print_array_in_range5(a, l, r);
}
template <typename T>
inline void print_array_in_range7(T* a, int l, int r) {
  for (int(i) = (r); (i) >= (l); --(i)) println(a[i]);
}
template <typename T>
inline void print_array_in_range8(T* a, int l, int r) {
  println(r - l + 1), print_array_in_range7(a, l, r);
}
template <typename T>
inline void print_array_in_range9(T* a, int l, int r) {
  print_space(r - l + 1), print_array_in_range1(a, l, r);
}
template <typename T>
inline void print_array_in_range10(T* a, int l, int r) {
  print_space(r - l + 1), print_array_in_range3(a, l, r);
}
template <typename T>
inline void print_array_in_range11(T* a, int l, int r) {
  print_space(r - l + 1), print_array_in_range5(a, l, r);
}
template <typename T>
inline void print_array_in_range12(T* a, int l, int r) {
  print_space(r - l + 1), print_array_in_range7(a, l, r);
}
template <typename T>
inline void print_array_in_range13(T* a, int l, int r, int n) {
  println(n), print_array_in_range1(a, l, r);
}
template <typename T>
inline void print_array_in_range14(T* a, int l, int r, int n) {
  println(n), print_array_in_range1(a, l, r);
}
template <typename T>
inline void print_array_in_range15(T* a, int l, int r, int n) {
  println(n), print_array_in_range1(a, l, r);
}
template <typename T>
inline void print_array_in_range16(T* a, int l, int r, int n) {
  println(n), print_array_in_range1(a, l, r);
}
template <typename T>
inline void print_array_in_range17(T* a, int l, int r, int n) {
  print_space(n), print_array_in_range1(a, l, r);
}
template <typename T>
inline void print_array_in_range18(T* a, int l, int r, int n) {
  print_space(n), print_array_in_range1(a, l, r);
}
template <typename T>
inline void print_array_in_range19(T* a, int l, int r, int n) {
  print_space(n), print_array_in_range1(a, l, r);
}
template <typename T>
inline void print_array_in_range20(T* a, int l, int r, int n) {
  print_space(n), print_array_in_range1(a, l, r);
}
template <typename T>
inline void print_array1(T* a, int n) {
  print_array_in_range1(a, 1, n);
}
template <typename T>
inline void print_array2(T* a, int n) {
  println(n), print_array1(a, n);
}
template <typename T>
inline void print_array3(T* a, int n) {
  print_array_in_range3(a, 1, n);
}
template <typename T>
inline void print_array4(T* a, int n) {
  println(n), print_array3(a, n);
}
template <typename T>
inline void print_array5(T* a, int n) {
  print_array_in_range5(a, 1, n);
}
template <typename T>
inline void print_array6(T* a, int n) {
  println(n), print_array5(a, n);
}
template <typename T>
inline void print_array7(T* a, int n) {
  print_array_in_range7(a, 1, n);
}
template <typename T>
inline void print_array8(T* a, int n) {
  println(n), print_array7(a, n);
}
template <typename T>
inline void print_array9(T* a, int n) {
  print_space(n), print_array1(a, n);
}
template <typename T>
inline void print_array10(T* a, int n) {
  print_space(n), print_array3(a, n);
}
template <typename T>
inline void print_array11(T* a, int n) {
  print_space(n), print_array5(a, n);
}
template <typename T>
inline void print_array12(T* a, int n) {
  print_space(n), print_array7(a, n);
}
template <typename T>
inline void vector_print(vector<T> a, int l, int r) {
  for (int(i) = (l); (i) <= (r); ++(i)) print_char(a[i], " \n"[i == r]);
}
template <typename T>
inline void map_print(map<T, T> a, int l, int r) {
  for (int(i) = (l); (i) <= (r); ++(i)) print_char(a[i], " \n"[i == r]);
}
template <typename T>
inline void stack_print(stack<T> a, char ch) {
  while (!a.empty()) print_char(a.top(), ch), a.pop();
}
template <typename T>
inline void queue_print(queue<T> a, char ch) {
  while (!a.empty()) print_char(a.front(), ch), a.pop();
}
template <typename T>
inline void pq_print(priority_queue<T> a, char ch) {
  while (!a.empty()) print_char(a.top(), ch), a.pop();
}
inline void print_string_in_range(string s, int l, int r) {
  for (int(i) = (l); (i) <= (r); ++(i)) putchar(s[i]);
}
inline void print_chars_in_range(char* a, int l, int r) {
  for (int(i) = (l); (i) <= (r); ++(i)) putchar(a[i]);
}
inline void print_allstring(string s) {
  print_string_in_range(s, 0, (int)s.size() - 1);
}
inline void filein(string s) { freopen((s + ".in").c_str(), "r", stdin); }
inline void fileout(string s) { freopen((s + ".out").c_str(), "w", stdout); }
inline void file(string s) { filein(s), fileout(s); }
}  // namespace fastExpress
using namespace fastExpress;
const int N = 207;
const long long inf = 0x3f3f3f3f3f3f3f3fll;
int n, t, K, a[N], d[N];
long long suma[N], sumd[N], lim[N], f[N][N][2], g[N][N][2], t1, t2, rem, vis;
int main() {
  n = read<int>(), t = read<int>(), K = read<int>();
  for (int(i) = (1); (i) <= (n); ++(i))
    a[i] = read<int>(), d[i] = read<int>(), lim[i] = read<long long>();
  n++, a[n] = d[n] = 0x3f3f3f3f, lim[n] = inf;
  for (int(i) = (1); (i) <= (n); ++(i))
    suma[i] = suma[i - 1] + a[i], sumd[i] = sumd[i - 1] + d[i];
  memset(f, 63, sizeof(f)), memset(g, 63, sizeof(g));
  memset(f, 0, sizeof *f), memset(g, 0, sizeof *g);
  for (int(i) = (1); (i) <= (n); ++(i))
    for (int(j) = (0); (j) <= (t); ++(j))
      for (int(k) = (0); (k) <= (1); ++(k)) {
        if (1ll * k * a[i] + 1ll * j * d[i] <= lim[i] && f[i - 1][j][k] < inf) {
          f[i][j][k] = min(f[i][j][k], f[i - 1][j][k]),
          t1 = (k * suma[i - 1] + j * sumd[i - 1] + K - 1) / K;
          if (t1 * K <= k * suma[i] + j * sumd[i])
            g[i][j][k] = min(g[i][j][k], t1);
        }
        for (int(r) = (0); (r) <= (j - 1); ++(r))
          if ((t1 = g[i][r][k]) != inf) {
            rem = k * suma[i] + r * sumd[i] - K * t1,
            vis = (max(0ll, rem + 1ll * (j - r) * d[i] - lim[i]) + K - 1) / K;
            if (vis * K <= rem && f[i - 1][j - r][0] < inf) {
              f[i][j][k] = min(f[i][j][k], t1 + vis + f[i - 1][j - r][0]),
              t2 = ((j - r) * sumd[i - 1] + K - 1) / K;
              if (t2 * K <= (j - r) * sumd[i] + (rem - vis * K))
                g[i][j][k] = min(g[i][j][k], t1 + vis + t2);
            }
          }
      }
  return write(f[n][t][1]), 0;
}