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.*;
import java.math.*;
import java.util.*;

public class C_test3 {
	public static void sortbyColumn(long arr[][], int col) 
    { 
        // Using built-in sort function Arrays.sort 
        Arrays.parallelSort(arr, new Comparator<long[]>() { 
            
          @Override              
          // Compare values according to columns 
          public int compare(final long[] entry1,  
                             final long[] entry2) { 
  
            // To sort in descending order revert  
            // the '>' Operator 
            if (entry1[col] > entry2[col]) 
                return 1; 
            else
                return -1; 
          } 
        });  // End of function call sort(). 
    } 
	public static void sort(long arr[], long arr2[]) 
    { 
        int n = arr.length; 
        for (int i = 1; i < n; ++i) { 
            long key = arr[i]; 
            long key2 = arr2[i];
            int j = i - 1; 
            while (j >= 0 && arr[j] > key || (j >= 0 && arr[j] == key && arr2[j] > key2)) { 
                arr[j + 1] = arr[j]; 
                arr2[j+1] = arr2[j];
                j = j - 1; 
            } 
//            while (j >= 0 && arr[j] == key && arr2[j] > arr2[i]) {
//            	arr[j+1] = arr[j];
//            	arr2[j+1] = arr2[j];
//            	j--;
//            }
            arr[j + 1] = key;
            arr2[j+1] = key2;
        } 
    } 
    public static void main(String[] args) throws IOException {
        FastScanner sc = new FastScanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        
        int people = sc.nextInt();
        int slices = sc.nextInt();
        long[][] arr = new long[people][3];
        for (int i = 0; i < arr.length; i++) {
        	arr[i][0] = sc.nextInt();
        	arr[i][1] = sc.nextInt();
        	arr[i][2] = sc.nextInt();
        }
        long pizzas = 0;
        long pizza1 = 0;
        long pizza2 = 0;
        long happiness = 0;
        for (int i = 0; i < arr.length; i++) {
        	pizzas += arr[i][0];
        	if (arr[i][1] > arr[i][2]) {
        		pizza1 += arr[i][0];
        		happiness += arr[i][1]*arr[i][0];
        	}
        	else {
        		pizza2 += arr[i][0];
        		happiness += arr[i][2]*arr[i][0];
        		//pw.println(arr[i][2]*arr[i][0]);
        	}
        }
        //pw.println(pizzas + " " + pizza1 + " " + pizza2);
        //pw.println("happiness = " + happiness);
        if (pizza1/slices+(pizza1%slices==0?0:1) + pizza2/slices+(pizza2%slices==0?0:1) == pizzas/slices + (pizzas%slices==0?0:1)) {
        	pw.println(happiness);
        }
        else {
        	// decrease pizza1 by pizza1 % slices, or decrease pizza2 by pizza2 % slices
        	// happiness will decrease by lowest of Math.abs(arr[i][2]-arr[i][1]) ..... 
        	// until the sum of arr[i][0] reaches pizza % slices
        	// sort 2d array of differences and iterate both cases
        	long[] a1 = new long[arr.length];
        	long[] a2 = new long[arr.length];
        	for (int i = 0; i < arr.length; i++) {
        		a1[i] = arr[i][0];
        		a2[i] = arr[i][1] - arr[i][2];
        	}
//        	sort(a2, a1);
        	long[][] diff = new long[arr.length][2];
        	for (int i = 0; i < diff.length; i++) {
        		diff[i][0] = a1[i];
        		diff[i][1] = a2[i];
        	}
        	//sortbyColumn(diff, 2);
        	Arrays.parallelSort(diff, new Comparator<long[]>() { 
                public int compare(long[] a2,  
                                   long[] a1) { 
                      Long a = a2[1];
                      Long b = a1[1];
                      return a.compareTo(b);
                } 
              }); 
        	//pw.println(Arrays.toString(a1));
        	//pw.println(Arrays.toString(a2));
        	int sum = 0;
        	int pos = 0;
        	long temp = happiness;
        	// switch people from pizza1 to pizza2
        	while (sum < pizza1 % slices) {
        		while (diff[pos][1] <= 0) {
        			pos++;
        		}
        		if (sum + diff[pos][0] > pizza1%slices) {
        			happiness -= (pizza1%slices-sum)*diff[pos][1];
        			break;
        		}
        		else {
        			sum += diff[pos][0];
        			happiness -= diff[pos][0]*diff[pos][1];
        			pos++;
        		}
        	}
        	sum = 0;
        	pos = arr.length-1;
        	// switch people from pizza2 to pizza1
        	while (sum < pizza2 % slices) {
        		while (diff[pos][1] > 0) {
        			pos--;
        		}
        		if (sum + diff[pos][0] > pizza2%slices) {
        			temp += (pizza2%slices-sum)*diff[pos][1];
        			break;
        		}
        		else {
        			sum += diff[pos][0];
        			temp += diff[pos][0]*diff[pos][1];
        			pos--;
        		}
        	}
        	pw.println(Math.max(happiness, temp));
        }
        
        pw.close();
    }
    static class FastScanner {
    	private boolean finished = false;

        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public FastScanner(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw   new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }
        public int peek() {
            if (numChars == -1) {
                return -1;
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    return -1;
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
        public long nextLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String nextString() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                if (Character.isValidCodePoint(c)) {
                    res.appendCodePoint(c);
                }
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private String readLine0() {
            StringBuilder buf = new StringBuilder();
            int c = read();
            while (c != '\n' && c != -1) {
                if (c != '\r') {
                    buf.appendCodePoint(c);
                }
                c = read();
            }
            return buf.toString();
        }
        public String readLine() {
            String s = readLine0();
            while (s.trim().length() == 0) {
                s = readLine0();
            }
            return s;
        }
        public String readLine(boolean ignoreEmptyLines) {
            if (ignoreEmptyLines) {
                return readLine();
            } else {
                return readLine0();
            }
        }

        public BigInteger readBigInteger() {
            try {
                return new BigInteger(nextString());
            } catch (NumberFormatException e) {
                throw new InputMismatchException();
            }
        }

        public char nextCharacter() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            return (char) c;
        }

        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E') {
                    return res * Math.pow(10, nextInt());
                }
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E') {
                        return res * Math.pow(10, nextInt());
                    }
                    if (c < '0' || c > '9') {
                        throw new InputMismatchException();
                    }
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        public boolean isExhausted() {
            int value;
            while (isSpaceChar(value = peek()) && value != -1) {
                read();
            }
            return value == -1;
        }
    public String next() {
            return nextString();
        }

        public SpaceCharFilter getFilter() {
            return filter;
        }

        public void setFilter(SpaceCharFilter filter) {
            this.filter = filter;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
        public int[] nextIntArray(int n){
            int[] array=new int[n];
            for(int i=0;i<n;++i)array[i]=nextInt();
            return array;
        }
        public int[] nextSortedIntArray(int n){
            int array[]=nextIntArray(n);
            PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
            for(int i = 0; i < n; i++){
                pq.add(array[i]);
            }
            int[] out = new int[n];
            for(int i = 0; i < n; i++){
                out[i] = pq.poll();
            }
            return out;
        }
        public int[] nextSumIntArray(int n){
            int[] array=new int[n];
            array[0]=nextInt();
            for(int i=1;i<n;++i)array[i]=array[i-1]+nextInt();
            return array;
        }
        public ArrayList<Integer>[] nextGraph(int n, int m){
            ArrayList<Integer>[] adj = new ArrayList[n];
            for(int i = 0; i < n; i++){
                adj[i] = new ArrayList<Integer>();
            }
            for(int i = 0; i < m; i++){
                int u = nextInt(); int v = nextInt();
                u--; v--;
                adj[u].add(v); adj[v].add(u);
            }
            return adj;
        }
        public ArrayList<Integer>[] nextTree(int n){
            return nextGraph(n, n-1);
        }

        public long[] nextLongArray(int n){
            long[] array=new long[n];
            for(int i=0;i<n;++i)array[i]=nextLong();
            return array;
        }
        public long[] nextSumLongArray(int n){
            long[] array=new long[n];
            array[0]=nextInt();
            for(int i=1;i<n;++i)array[i]=array[i-1]+nextInt();
            return array;
        }
        public long[] nextSortedLongArray(int n){
            long array[]=nextLongArray(n);
            Arrays.sort(array);
            return array;
        }
    }
	static void shuffle(int[] a) {
		Random get = new Random();
		for (int i = 0; i < a.length; i++) {
			int r = get.nextInt(a.length);
			int temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}
	static void shuffle(long[] a) {
		Random get = new Random();
		for (int i = 0; i < a.length; i++) {
			int r = get.nextInt(a.length);
			long temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}
}