865_B. Ordering Pizza_36795
It's another Start[c]up finals, and that means there is pizza to order for the onsite contestants. There are only 2 types of pizza (obviously not, but let's just pretend for the sake of the problem), and all pizzas contain exactly S slices.

It is known that the i-th contestant will eat si slices of pizza, and gain ai happiness for each slice of type 1 pizza they eat, and bi happiness for each slice of type 2 pizza they eat. We can order any number of type 1 and type 2 pizzas, but we want to buy the minimum possible number of pizzas for all of the contestants to be able to eat their required number of slices. Given that restriction, what is the maximum possible total happiness that can be achieved?

Input

The first line of input will contain integers N and S (1 ≤ N ≤ 105, 1 ≤ S ≤ 105), the number of contestants and the number of slices per pizza, respectively. N lines follow.

The i-th such line contains integers si, ai, and bi (1 ≤ si ≤ 105, 1 ≤ ai ≤ 105, 1 ≤ bi ≤ 105), the number of slices the i-th contestant will eat, the happiness they will gain from each type 1 slice they eat, and the happiness they will gain from each type 2 slice they eat, respectively.

Output

Print the maximum total happiness that can be achieved.

Examples

Input

3 12
3 5 7
4 6 7
5 9 5


Output

84


Input

6 10
7 4 7
5 8 8
12 5 8
6 11 6
3 3 7
5 9 6


Output

314

Note

In the first example, you only need to buy one pizza. If you buy a type 1 pizza, the total happiness will be 3·5 + 4·6 + 5·9 = 84, and if you buy a type 2 pizza, the total happiness will be 3·7 + 4·7 + 5·5 = 74.
#include <bits/stdc++.h>
struct St {
  int h, h1, h2, nom, type;
};
bool operator<(St a, St b) { return a.h1 - a.h2 > b.h1 - b.h2; }
St st[200000];
int k[100000];
int i, n, n2;
long long s, npart, a, b, c, d, npitca, fa, fb, fc, fd;
int cnt[100001];
long long sum(long long npi_1) {
  long long npi_2 = npitca - npi_1;
  long long npart_1 = npi_1 * npart, npart_2 = npi_2 * npart;
  long long count;
  long long ans = 0;
  int i, nom;
  for (i = 0; i < n; i++) cnt[i] = k[i];
  for (i = 0; i < n2; i++) {
    nom = st[i].nom;
    if (cnt[nom] == 0) continue;
    if (st[i].type == 1) {
      if (npart_1 == 0) continue;
      count = cnt[nom];
      if (count > npart_1) count = npart_1;
      ans = ans + count * st[i].h;
      npart_1 = npart_1 - count;
      cnt[nom] = cnt[nom] - count;
    } else {
      if (npart_2 == 0) continue;
      count = cnt[nom];
      if (count > npart_2) count = npart_2;
      ans = ans + count * st[i].h;
      npart_2 = npart_2 - count;
      cnt[nom] = cnt[nom] - count;
    }
  }
  return ans;
}
using namespace std;
int main() {
  scanf("%d %d", &n, &npart);
  s = 0;
  for (i = 0; i < n; i++) {
    int ha, hb;
    scanf("%d %d %d", &k[i], &ha, &hb);
    st[n2].nom = i;
    st[n2].h = ha;
    st[n2].h1 = ha;
    st[n2].h2 = hb;
    st[n2++].type = 1;
    st[n2].nom = i;
    st[n2].h = hb;
    st[n2].h1 = hb;
    st[n2].h2 = ha;
    st[n2++].type = 2;
    s = s + k[i];
  }
  npitca = s / npart;
  if (npitca * npart < s) npitca++;
  sort(st, st + n2);
  a = 0;
  b = npitca;
  while (a < b) {
    c = a + (b - a) / 3;
    d = b - (b - a) / 3;
    fc = sum(c);
    fd = sum(d);
    if (fc == fd)
      a = c + 1, b = d;
    else if (fc < fd)
      a = c + 1;
    else
      b = d - 1;
  }
  cout << sum(a) << endl;
}

3 12
3 5 7
4 6 7
5 9 5
 6 10
7 4 7
5 8 8
12 5 8
6 11 6
3 3 7
5 9 6
 1 100
97065 97644 98402
 1 100000
1 82372 5587
 2 10
9 1 2
9 2 1
 3 10
10 3 4
5 1 100
5 100 1
 2 100000
50000 1 100000
50000 100000 1
 3 5
6 4 5
6 5 5
8 7 5
 3 4
2 1 10
1 2 1
1 3 1
 25 6
1 10 5
1 8 4
1 8 2
4 8 9
3 2 8
1 9 5
2 10 10
3 9 6
3 5 4
2 7 8
2 3 2
2 6 8
3 7 8
4 3 7
1 8 1
3 6 4
3 2 8
2 2 1
4 8 8
4 8 4
3 10 2
3 6 6
2 2 5
1 6 2
4 1 5
 3 3
6 5 6
2 5 4
2 4 5
 2 3
5 5 10
5 10 5
 2 3
2 10 1
2 1 10
 10 8
7 1 4
4 8 9
3 4 10
5 5 9
1 5 6
1 8 5
5 7 4
5 4 6
10 5 7
9 7 3
 2 9
6 1 7
6 7 1
 3 5
2 7 4
6 5 9
6 5 6
 2 10
7 2 1
7 1 2
 2 3
5 10 5
5 5 10
 1 100
154860 97644 98402
 1 100000
1 82372 3601
 2 10
0 1 2
9 2 1
 3 10
10 0 4
5 1 100
5 100 1
 3 5
6 4 5
6 5 5
8 7 9
 2 4
2 1 10
1 2 1
1 3 1
 25 6
1 10 5
1 8 4
1 8 2
4 8 9
3 2 8
1 9 5
2 10 10
1 9 6
3 5 4
2 7 8
2 3 2
2 6 8
3 7 8
4 3 7
1 8 1
3 6 4
3 2 8
2 2 1
4 8 8
4 8 4
3 10 2
3 6 6
2 2 5
1 6 2
4 1 5
 3 3
11 5 6
2 5 4
2 4 5
 2 3
5 5 10
5 12 5
 10 8
7 1 4
4 8 9
3 5 10
5 5 9
1 5 6
1 8 5
5 7 4
5 4 6
10 5 7
9 7 3
 2 9
5 1 7
6 7 1
 3 5
2 5 4
6 5 9
6 5 6
 2 13
7 2 1
7 1 2
 2 3
5 10 9
5 5 10
 3 12
3 5 0
4 6 7
5 9 5
 1 100
127954 97644 98402
 2 10
0 1 2
16 2 1
 3 13
10 0 4
5 1 100
5 100 1
 2 4
2 1 10
1 2 2
1 3 1
 25 6
1 10 5
1 8 4
1 8 2
4 8 9
3 2 8
1 9 5
2 10 10
1 9 6
3 5 4
2 7 8
2 3 2
2 6 8
3 7 8
4 3 7
1 8 1
3 6 4
3 2 8
2 2 1
4 8 8
4 13 4
3 10 2
3 6 6
2 2 5
1 6 2
4 1 5
 2 9
5 1 7
6 9 1
 2 3
5 10 9
9 5 10
 1 100
127954 98475 98402
 25 6
1 10 5
1 8 4
1 5 2
4 8 9
3 2 8
1 9 5
2 10 10
1 9 6
3 5 4
2 7 8
2 3 2
2 6 8
3 7 8
4 3 7
1 8 1
3 6 4
3 2 8
2 2 1
4 8 8
4 13 4
3 10 2
3 6 6
2 2 5
1 6 2
4 1 5
 3 8
2 10 4
6 5 9
6 5 6
 3 12
3 5 0
4 6 3
5 4 5
 6 10
7 4 7
2 16 8
12 5 8
6 11 6
3 0 7
5 9 6
 2 4
2 1 10
2 0 2
1 3 1
 2 3
5 10 4
3 12 5
 10 15
7 1 4
4 8 9
3 7 10
5 5 9
1 5 6
1 8 5
5 7 4
5 4 6
10 5 12
9 7 3
 2 13
0 1 1
7 0 2
 6 10
7 4 7
1 16 8
12 5 8
6 11 6
3 0 7
5 9 6
 25 6
1 10 5
1 8 4
1 5 2
4 8 9
4 2 8
1 9 5
2 10 10
1 9 6
3 5 4
2 7 8
2 3 0
2 6 8
3 7 8
4 3 7
1 8 1
3 6 4
3 2 8
2 2 1
4 8 8
4 13 4
3 10 2
3 6 6
2 2 5
1 6 2
4 1 5
 10 15
7 1 4
4 8 9
3 7 10
5 5 9
2 5 6
1 8 5
5 7 4
5 4 6
10 5 12
9 7 3
 3 8
2 10 4
6 3 5
6 5 6
 2 10
5 10 9
11 5 10
 6 1
7 4 7
1 16 8
12 5 8
6 11 6
3 0 7
5 9 6
 6 10
7 4 7
5 16 8
12 5 8
6 11 6
3 3 7
5 9 6
 2 3
5 10 10
5 12 5
 10 8
7 1 4
4 8 9
3 7 10
5 5 9
1 5 6
1 8 5
5 7 4
5 4 6
10 5 7
9 7 3
 3 8
2 5 4
6 5 9
6 5 6
 2 13
7 2 1
7 0 2
 3 12
3 5 0
4 6 3
5 9 5
 6 10
7 4 7
5 16 8
12 5 8
6 11 6
3 0 7
5 9 6
 2 4
2 1 10
1 0 2
1 3 1
 2 3
5 10 4
5 12 5
 10 15
7 1 4
4 8 9
3 7 10
5 5 9
1 5 6
1 8 5
5 7 4
5 4 6
10 5 7
9 7 3
 2 13
7 1 1
7 0 2
 2 5
5 10 9
9 5 10
 25 6
1 10 5
1 8 4
1 5 2
4 8 9
3 2 8
1 9 5
2 10 10
1 9 6
3 5 4
2 7 8
2 3 0
2 6 8
3 7 8
4 3 7
1 8 1
3 6 4
3 2 8
2 2 1
4 8 8
4 13 4
3 10 2
3 6 6
2 2 5
1 6 2
4 1 5
 3 8
2 10 4
6 5 5
6 5 6
 2 10
5 10 9
9 5 10
 3 12
3 5 1
4 6 3
5 4 5
 2 7
2 1 10
2 0 2
1 3 1
 2 3
5 10 4
3 16 5
 2 13
0 0 1
7 0 2
 3 12
3 5 0
7 6 3
5 4 5
 2 7
2 1 10
2 0 2
1 4 1
 25 6
1 10 5
1 8 4
1 5 2
4 8 9
4 2 8
1 9 5
2 10 10
1 9 6
3 5 3
2 7 8
2 3 0
2 6 8
3 7 8
4 3 7
1 8 1
3 6 4
3 2 8
2 2 1
4 8 8
4 13 4
3 10 2
3 6 6
2 2 5
1 6 2
4 1 5

84
 314
 9551390130
 82372
 36
 1035
 5000050000
 116
 22
 449
 56
 100
 40
 351
 84
 102
 28
 100
 15238533720
 82372
 18
 1020
 132
 21
 431
 85
 110
 351
 77
 98
 28
 100
 84
 12590929508
 32
 1032
 22
 451
 89
 140
 12600270150
 448
 106
 59
 303
 24
 86
 401
 14
 287
 456
 407
 82
 155
 293
 351
 110
 351
 98
 28
 84
 351
 22
 110
 351
 21
 140
 448
 86
 140
 59
 24
 98
 14
 82
 24
 456
