Một ngày nọ, phòng kỹ thuật của một công ty được yêu cầu phải thực hiện \(m\) công việc, công việc thứ \(i\) có \(k_i\) phần. Họ phải hoàn thành hết tất cả công việc đó trong vòng \(n\) ngày được đánh số từ ngày \(1\) đến ngày \(n\). Được biết phòng kỹ thuật có một siêu máy tính có thể chứa rất nhiều lõi. Mỗi lõi có khả năng thực hiện và hoàn thành một phần của một công việc bất kỳ trong đúng một ngày, các phần của một công việc có thể được thực hiện và hoàn thành một cách song song và không cần liên tiếp (tức là có thể thực hiện các phần trong một hoặc nhiều ngày). Một công việc được hoàn thành khi và chỉ khi tất cả các phần của công việc đó được hoàn thành. Biết rằng công việc thứ \(i\) chỉ có thể được thực hiện và hoàn thành từ đầu ngày \(s_i\) đến hết ngày \(t_i\), vì chi phí lắp đặt và bảo trì rất tốn kém nên trưởng phòng kỹ thuật muốn sử dụng ít lõi nhất có thể.

Yêu cầu: Tính số lượng lõi ít nhất cần phải lắp đặt sao cho vẫn đảm bảo hoàn thành hết \(m\) công việc trong \(n\) ngày.

Input

• Dòng đầu tiên chứa hai số nguyên \(m\) và \(n\) \((1 \leq m \leq 10^5, 1 \leq n \leq 10^9)\) lần lượt là số lượng công việc và số ngày thực hiện.
• Trong \(m\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(k_i\), \(s_i\) và \(t_i\) \((1 \leq k_i \leq 10^{12}, 1 \leq s_i \leq t_i \leq n)\) là số lượng phần và thời điểm giới hạn thực hiện công việc thứ \(i\).

Output

• In ra kết quả của yêu cầu bài toán.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(s_i = t_i\).
• Subtask \(2\) (\(30\%\) số điểm): \(m \leq 500\), \(n \leq 10^6\) và \(k_i \leq 500\).
• Subtask \(3\) (\(30\%\) số điểm): \(k_i = 1\).
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 4
3 1 3
2 2 4
4 1 4

3

4 3
1 1 3
4 3 3
2 2 3
2 1 2

4