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.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.atomic.AtomicLong;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Main2 {

    static long mod = 1000000007L;
    static FastScanner scanner;

    static long m;
    static long k;

    public static void main(String[] args) {
        scanner = new FastScanner();
        int n = scanner.nextInt();
        long s = scanner.nextInt();
        Person[] persons = new Person[n];
        List<Person> groupA = new ArrayList<>();
        List<Person> groupB = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            persons[i] = new Person(scanner);
            if (persons[i].a > persons[i].b) {
                groupA.add(persons[i]);
            } else {
                groupB.add(persons[i]);
            }
        }

        long sumAll = Stream.of(persons).mapToLong(p -> p.s).sum();
        long pizas = sumAll / s + (sumAll % s == 0 ? 0 : 1);
        long sumA = groupA.stream().mapToLong(p -> p.s).sum();
        long pizasA = sumA / s;

        pizasA = Math.max(0, pizasA - 1);

        BigInteger max = BigInteger.ZERO;
        for (int i = 0; i < 3; i++) {
            long pa = pizasA + i;
            long pb = pizas - pa;
            if (pb < 0) break;
            BigInteger current = calculate(pa * s, pb * s, persons);
            max = max.max(current);
        }
        System.out.println(max);
    }

    static BigInteger calculate(long a, long b, Person[] persons) {
        Person[] copy = new Person[persons.length];
        List<Person> groupB = new ArrayList<>();
        List<Person> groupA = new ArrayList<>();
        for (int i = 0; i < persons.length; i++) {
            copy[i] = new Person(persons[i].s, persons[i].a, persons[i].b);
            if (persons[i].a == persons[i].b) {
                continue;
            }
            if (persons[i].a > persons[i].b) groupA.add(copy[i]); else groupB.add(copy[i]);
        }
        groupB.sort((x, y) -> -Long.compare((x.b - x.a), (y.b - y.a)));
        groupA.sort((x, y) -> -Long.compare((x.a - x.b), (y.a - y.b)));

        BigInteger sumAll = BigInteger.ZERO;
        for (Person aPerson : groupA) {
            long toEat = Math.min(a, aPerson.s);
            sumAll = sumAll.add(BigInteger.valueOf(aPerson.a * toEat));
            a -= toEat;
            aPerson.s -= toEat;
        }
        for (Person bPerson : groupB) {
            long toEat = Math.min(b, bPerson.s);
            sumAll = sumAll.add(BigInteger.valueOf(bPerson.b * toEat));
            b -= toEat;
            bPerson.s -= toEat;
        }

        for (Person person : copy) {
            if (person.s == 0) continue;
            while (person.s > 0) {
                if (a == 0) {
                    long toEat = Math.min(b, person.s);
                    sumAll = sumAll.add(BigInteger.valueOf(person.b * toEat));
                    person.s -= toEat;
                    b -= toEat;
                } else {
                    long toEat = Math.min(a, person.s);
                    sumAll = sumAll.add(BigInteger.valueOf(person.a * toEat));
                    person.s -= toEat;
                    a -= toEat;
                }
            }
        }
        return sumAll;
    }

    static class Person {
        long s, a, b;

        public Person(long s, long a, long b) {
            this.s = s;
            this.a = a;
            this.b = b;
        }

        public Person(FastScanner scanner) {
            s = scanner.nextInt();
            a = scanner.nextInt();
            b = scanner.nextInt();
        }
    }

    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String nextToken() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String nextLine() {
            try {
                return br.readLine();
            } catch (Exception e) {
                e.printStackTrace();
                throw new RuntimeException();
            }
        }

        int nextInt() {
            return Integer.parseInt(nextToken());
        }

        long nextLong() {
            return Long.parseLong(nextToken());
        }

        double nextDouble() {
            return Double.parseDouble(nextToken());
        }

        int[] nextIntArray(int n) {
            int[] res = new int[n];
            for (int i = 0; i < n; i++) res[i] = nextInt();
            return res;
        }

        long[] nextLongArray(int n) {
            long[] res = new long[n];
            for (int i = 0; i < n; i++) res[i] = nextLong();
            return res;
        }

        String[] nextStringArray(int n) {
            String[] res = new String[n];
            for (int i = 0; i < n; i++) res[i] = nextToken();
            return res;
        }
    }

    static class PrefixSums {
        long[] sums;

        public PrefixSums(long[] sums) {
            this.sums = sums;
        }

        public long sum(int fromInclusive, int toExclusive) {
            if (fromInclusive > toExclusive) throw new IllegalArgumentException("Wrong sum");
            return sums[toExclusive] - sums[fromInclusive];
        }

        public static PrefixSums of(int[] ar) {
            long[] sums = new long[ar.length + 1];
            for (int i = 1; i <= ar.length; i++) {
                sums[i] = sums[i - 1] + ar[i - 1];
            }
            return new PrefixSums(sums);
        }

        public static PrefixSums of(long[] ar) {
            long[] sums = new long[ar.length + 1];
            for (int i = 1; i <= ar.length; i++) {
                sums[i] = sums[i - 1] + ar[i - 1];
            }
            return new PrefixSums(sums);
        }
    }

    static class ADUtils {
        static void sort(int[] ar) {
            Random rnd = ThreadLocalRandom.current();
            for (int i = ar.length - 1; i > 0; i--)
            {
                int index = rnd.nextInt(i + 1);
                // Simple swap
                int a = ar[index];
                ar[index] = ar[i];
                ar[i] = a;
            }
            Arrays.sort(ar);
        }

        static void sort(long[] ar) {
            Random rnd = ThreadLocalRandom.current();
            for (int i = ar.length - 1; i > 0; i--)
            {
                int index = rnd.nextInt(i + 1);
                // Simple swap
                long a = ar[index];
                ar[index] = ar[i];
                ar[i] = a;
            }
            Arrays.sort(ar);
        }
    }

    static class MathUtils {
        static long modpow(long b, long e, long m) {
            long result = 1;

            while (e > 0) {
                if ((e & 1) == 1) {
            /* multiply in this bit's contribution while using modulus to keep
             * result small */
                    result = (result * b) % m;
                }
                b = (b * b) % m;
                e >>= 1;
            }

            return result;
        }

        static long submod(long x, long y, long m) {
            return (x - y + m) % m;
        }
    }
}

//3 3