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.
/**
 * DA-IICT
 * Author : PARTH PATEL
 */
import java.io.*;
import java.math.*;
import java.util.*;

import static java.util.Arrays.fill;
import static java.lang.Math.*;
import static java.util.Arrays.sort;
import static java.util.Collections.sort;


public class C867 {

	public static int mod = 1000000007;
	static FasterScanner in = new FasterScanner();
	static PrintWriter out = new PrintWriter(System.out);
	static class Pair implements Comparable<Pair>
	{
		long s;
		long a;
		long b;
		int pizza;
		Pair(long s,long a,long b,int pizza)
		{
			this.s=s;
			this.a=a;
			this.b=b;
			this.pizza=pizza;
		}
		@Override
		public int compareTo(Pair o) {
			long abs1=abs(this.a-this.b);
			long abs2=abs(o.a-o.b);
			if(abs1==abs2)
				return 0;
			 return abs1 - abs2 <0 ? -1 : 1;
		}
	}
	public static void main(String[] args) {

		int n=in.nextInt();
		int s=in.nextInt();
		long[] si=new long[n+1];
		long[] ai=new long[n+1];
		long[] bi=new long[n+1];
		Pair[] arr=new Pair[n+1];
		arr[0]=new Pair(1, 1, 1,-1);
		for(int i=1;i<=n;i++)
		{
			si[i]=in.nextInt();
			ai[i]=in.nextInt();
			bi[i]=in.nextInt();
			int pizza=0;
			if(ai[i]>bi[i])
				pizza=1;
			else
				pizza=2;
			arr[i]=new Pair(si[i], ai[i], bi[i],pizza);
		}
		long maxhappiness=0;
		long pizza1=0;
		long pizza2=0;
		for(int i=1;i<=n;i++)
		{
			if(ai[i]>bi[i])
			{
				maxhappiness+=si[i]*ai[i];
				pizza1+=si[i];
			}
			else
			{
				maxhappiness+=si[i]*bi[i];
				pizza2+=si[i];
			}
		}
		if(pizza1%s==0 || pizza2%s==0 || (pizza1%s+pizza2%s)>s)
		{
			System.out.println(maxhappiness);
			return;
		}
		else
		{
			Arrays.sort(arr);
		/*	for(int i=1;i<=n;i++)
				out.println(arr[i].s+" "+arr[i].a+" "+arr[i].b);*/
			//now it is clear that pizza1%s>0 && pizza2%s>0 && (pizza1%s+pizza2%s)<=s
			//we are shifting everyone to pizza2 greedily
			//System.out.println(arr[0].a+" "+arr[0].b);
			long temppizza1=pizza1%s;
			long temppizza2=pizza2%s;
			long temphappiness1=maxhappiness;
			long temphappiness2=maxhappiness;
		//	System.out.println(pizza1+" "+pizza2+" "+maxhappiness);
			for(int i=1;i<=n;i++)
			{
				if(arr[i].pizza==2)
					continue;
				long take=min(arr[i].s, temppizza1);
				temppizza1-=take;
				temppizza2+=take;
				temphappiness1+=(arr[i].b-arr[i].a)*take;
				if(temppizza1==0 || (temppizza1%s+temppizza2%s)>s)
					break;
			}
			//we will now shift everyone to pizza1 greedily
			temppizza1=pizza1%s;
			temppizza2=pizza2%s;
			for(int i=1;i<=n;i++)
			{
				if(arr[i].pizza==1)
					continue;
				long take=min(arr[i].s, temppizza2);
				temppizza1+=take;
				temppizza2-=take;
				//System.out.println(temphappiness2);
				temphappiness2+=(arr[i].a-arr[i].b)*take;
				//System.out.println(temphappiness2);
				if(  temppizza2%s==0 || (temppizza1%s+temppizza2%s)>s)
					break;
			}
			out.println(max(temphappiness1, temphappiness2));
		}
		out.close();

	}

	/////////////////SEGMENT TREE (BUILD-UPDATE-QUERY)/////////////////////////////
	/////////////////UPDATE FOLLOWING METHODS AS PER NEED//////////////////////////
	/*
	public static void buildsegmenttree(int node,int start,int end)
	{
		if(start==end)
		{
			// Leaf node will have a single element
			segmenttree[node]=arr[start];
		}
		else
		{
			int mid=start+(end-start)/2;
			// Recurse on the left child
			buildsegmenttree(2*node, start, mid);
			// Recurse on the right child
			buildsegmenttree(2*node+1, mid+1, end);
			// Internal node will have the sum of both of its children
			segmenttree[node]=segmenttree[2*node]+segmenttree[2*node+1];
		}
	}
	
	public static void updatesegmenttree(int node,int start,int end,int idx,int val)
	{
		if(start==end)
		{
			//Leaf Node
			arr[idx]+=val;
			segmenttree[node]+=val;
		}
		else
		{
			int mid=start+(end-start)/2;
			if(start<=idx && idx<=mid)
			{
				// If idx is in the left child, recurse on the left child
				updatesegmenttree(2*node, start, mid, idx, val);
			}
			else
			{
				// if idx is in the right child, recurse on the right child
				updatesegmenttree(2*node+1, mid+1, end, idx, val);
			}
			// Internal node will have the sum of both of its children
			segmenttree[node]=segmenttree[2*node]+segmenttree[2*node+1];
		}
	}
	
	public static long querysegmenttree(int node,int start,int end,int l,int r)
	{
		if(r<start || end<l)
		{
			// range represented by a node is completely outside the given range
			return 0;
		}
		if(l <= start && end <= r)
	    {
	        // range represented by a node is completely inside the given range
	        return segmenttree[node];
	    }
		// range represented by a node is partially inside and partially outside the given range
		int mid=start+(end-start)/2;
		long leftchild=querysegmenttree(2*node, start, mid, l, r);
		long rightchild=querysegmenttree(2*node+1, mid+1, end, l, r);
		return (leftchild+rightchild);
	}
	*/

	public static long pow(long x, long n, long mod) {
		long res = 1;
		for (long p = x; n > 0; n >>= 1, p = (p * p) % mod) {
			if ((n & 1) != 0) {
				res = (res * p % mod);
			}
		}
		return res;
	}

	public static long gcd(long n1, long n2) {
		long r;
		while (n2 != 0) {
			r = n1 % n2;
			n1 = n2;
			n2 = r;
		}
		return n1;
	}

	public static long lcm(long n1, long n2) {
		long answer = (n1 * n2) / (gcd(n1, n2));
		return answer;
	}

	static class FasterScanner {
		private byte[] buf = new byte[1024];
		private int curChar;
		private int snumChars;

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

		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}

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

		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 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 int[] nextIntArray(int n) {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = nextInt();
			}
			return arr;
		}

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

		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}
	}

}
