Problem: Joisino is planning to record N TV programs with recorders.

The TV can receive C channels numbered 1 through C.

The i-th program that she wants to record will be broadcast from time s_i to time t_i (including time s_i but not t_i) on Channel c_i.

Here, there will never be more than one program that are broadcast on the same channel at the same time.

When the recorder is recording a channel from time S to time T (including time S but not T), it cannot record other channels from time S-0.5 to time T (including time S-0.5 but not T).

Find the minimum number of recorders required to record the channels so that all the N programs are completely recorded.

Constraints

* 1≤N≤10^5
* 1≤C≤30
* 1≤s_i<t_i≤10^5
* 1≤c_i≤C
* If c_i=c_j and i≠j, either t_i≤s_j or s_i≥t_j.
* All input values are integers.

Input

Input is given from Standard Input in the following format:


N C
s_1 t_1 c_1
:
s_N t_N c_N


Output

When the minimum required number of recorders is x, print the value of x.

Examples

Input

3 2
1 7 2
7 8 1
8 12 1


Output

2


Input

3 4
1 3 2
3 4 4
1 4 3


Output

3


Input

9 4
56 60 4
33 37 2
89 90 3
32 43 1
67 68 3
49 51 3
31 32 3
70 71 1
11 12 3


Output

2

Solution (in JAVA):

Solution:
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;


public class Main {
	public static void main(String[] args) {


		slover();
		out.flush();
	}
	static FastScanner sc = new FastScanner();
	static PrintWriter out = new PrintWriter(System.out);
	//StringBuffer S = new StringBuffer(sc.next());
	//String hoge2 = str.reverse().toString();
	//map.containsKey(A)
	//Map<Integer, Integer> map = new HashMap<Integer, Integer>(N);
	/*for ( キーのデータ型 key : マップの名前.keySet() ) {
		データのデータ型 data = マップの名前.get( key );

		// keyやdataを使った処理;
	}*/
	//int i = Integer.parseInt(s);
	//Queue<String> qq=new ArrayDeque<>(); //add,poll,peek BFSは前から実行される
	//Deque<String> dd=new ArrayDeque<>();//push後ろに入れる,poll(pop)後ろからとる,peek addは先頭に入るからバグ注意
	//stackdfsは後ろから実行される
	//ArrayList<Integer> cc = new ArrayList<>(N);
	//cc.contains(tmp)
	//Arrays.asList(c).contains("a")
	//list.set(1,"walk");//1 1 2 3 5


	private static int INF =1000000007;


	private static int slover() {
		
		int N=sc.nextInt();
		int C=sc.nextInt();
		
		int x[][]=new int[200002][C];
		
		for(int i=0;i<N;i++) {
			
			
			int s=sc.nextInt();
			int t=sc.nextInt();
			int c=sc.nextInt();
			if(x[t*2-1][c-1]==1&&x[s*2][c-1]==-1) {
				x[s*2][c-1]=0;
				x[t*2-1][c-1]=0;
				continue;
			}
			
			if(x[s*2][c-1]==-1) {
				x[s*2][c-1]=0;
				x[t*2][c-1]--;
				continue;
			}
			if(x[t*2-1][c-1]==1) {
				x[s*2-1][c-1]++;
				x[t*2-1][c-1]=0;
				continue;
			}
			x[s*2-1][c-1]++;
			x[t*2][c-1]--;
		}
		int t=0;
		int ans=0;
		for(int i=0;i<200002;i++) {
			
			for(int a=0;a<C;a++) {
				t+=x[i][a];
			}
			ans=Math.max(t, ans);
			
			
		}
		p(ans);
		
		return 0;
	}






	static long Nsin(long t) {
		long sum=0;
		long v=1;
		long tt=1;
		for(long k=0;k<(t+"").length();k++) {
			sum+=(t%(tt*10)-t%tt)/tt*v;
			v*=t;
			tt*=10;
		}
		return sum;
	}

	static long so(long n) {
		for(long i=2;i*i<=n;i++) {
			if(n%i==0) {
				return i;
			}
		}
		return 0;

	}



	     static void nibun(int a,int b,int target) {

	    	 int ok=a;
	    	 int ng=b;


	    	 int t=2;

	    	 while(a<b) {
	    		 int G=(ok+ng)/2;
	    		 if(t==target) {
	    			 break;
	    		 }
	    		 if(t>ok) {

	    		 }
	    		 if(t>ng) {

	    		 }



	    	 }



	     }





		//StringBuffer str = new StringBuffer(sc.nextInt());
		//for(int i=0;i<N;i++) {}




			//	p("===================");
				//for(int f:gyo.keySet()){
				    //p(gyo.get(f));
			//	}
			//	p("===================");














	static void p(String ans) {out.println(ans);};
	static void p(int ans) {out.println(ans);};
	static void p() {out.println();};
	static void p(long ans) {out.println(ans);};
	static void p(double ans) {out.println(ans);};

	static void pn(String ans) {out.print(ans);};
	static void pn(int ans) {out.print(ans);};
	static void pn() {out.print("");};
	static void pn(long ans) {out.print(ans);};
	static void pn(double ans) {out.print(ans);};

	static class FastScanner {
	    private final InputStream in = System.in;
	    private final byte[] buffer = new byte[1024];
	    private int ptr = 0;
	    private int buflen = 0;

	    private boolean hasNextByte() {
	      if (ptr < buflen) {
	        return true;
	      } else {
	        ptr = 0;
	        try {
	          buflen = in.read(buffer);
	        } catch (IOException e) {
	          e.printStackTrace();
	        }
	        if (buflen <= 0) {
	          return false;
	        }
	      }
	      return true;
	    }

	    private int readByte() {
	      if (hasNextByte()) return buffer[ptr++];
	      else return -1;
	    }

	    private static boolean isPrintableChar(int c) {
	      return 33 <= c && c <= 126;
	    }

	    private void skipUnprintable() {
	      while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
	    }

	    public boolean hasNext() {
	      skipUnprintable();
	      return hasNextByte();
	    }

	    public String next() {
	      if (!hasNext()) throw new NoSuchElementException();
	      StringBuilder sb = new StringBuilder();
	      int b = readByte();
	      while (isPrintableChar(b)) {
	        sb.appendCodePoint(b);
	        b = readByte();
	      }
	      return sb.toString();
	    }

	    public long nextLong() {
	      if (!hasNext()) throw new NoSuchElementException();
	      long n = 0;
	      boolean minus = false;
	      int b = readByte();
	      if (b == '-') {
	        minus = true;
	        b = readByte();
	      }
	      if (b < '0' || '9' < b) {
	        throw new NumberFormatException();
	      }
	      while (true) {
	        if ('0' <= b && b <= '9') {
	          n *= 10;
	          n += b - '0';
	        } else if (b == -1 || !isPrintableChar(b)) {
	          return minus ? -n : n;
	        } else {
	          throw new NumberFormatException();
	        }
	        b = readByte();
	      }
	    }

	    public int nextInt() {
	      return (int) nextLong();
	    }

	    public double nextDouble(){
	    	return Double.parseDouble(next());
	    }

	    public int[] nextIntArray(int N, boolean oneBased) {
	      if (oneBased) {
	        int[] array = new int[N + 1];
	        for (int i = 1; i <= N; i++) {
	          array[i] = sc.nextInt();
	        }
	        return array;
	      } else {
	        int[] array = new int[N];
	        for (int i = 0; i < N; i++) {
	          array[i] = sc.nextInt();
	        }
	        return array;
	      }
	    }

	    public long[] nextLongArray(int N, boolean oneBased) {
	      if (oneBased) {
	        long[] array = new long[N + 1];
	        for (int i = 1; i <= N; i++) {
	          array[i] = sc.nextLong();
	        }
	        return array;
	      } else {
	        long[] array = new long[N];
	        for (int i = 0; i < N; i++) {
	          array[i] = sc.nextLong();
	        }
	        return array;
	      }
	    }
	  }
}