Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Sau vài tháng không thể ra ngoài vì COVID-19, giò đây Tèo đã có thể đi chơi thỏa thích. Tèo có một chiếc xe máy kỳ diệu, có thể chứa được lượng xăng tùy thích. Trước khi ròi khỏi nhà, Tèo đã đổ vào chiếc xe của mình \(F\) lít xăng.

Tèo muốn đi thăm một ngưòi bạn ở cách Tèo \(D\) km. Trên đưòng đi có \(N\) trạm xăng để Tèo đổ thêm xăng; trạm xăng thứ \(i\) cách nhà Tèo \(X_i\) km. ở trạm xăng thứ \(i\), Tèo có thể nạp thêm \(A_i\) lít xăng, nhưng chỉ khi lượng xăng ban đầu \(F\) không quá \(B_i\).

Hãy tìm lượng xăng ban đầu \(F\) nhỏ nhất sao cho Tèo có thể có đủ xăng để đến thăm bạn của mình.

Input

  • Dòng thứ nhất gồm hai số nguyên dương \(N\)\(D\)
  • Trong \(N\) dòng tiếp theo, mỗi dòng gồm ba số nguyên dương \(X_i,A_i, B_i\)

Output

  • In ra một số nguyên dương duy nhất là đáp án của bài toán.

Constraints

  • \(N < 3 \cdot 10^5, D < 10^9\)
  • \(X_i < D, A_i, B_i < 10^9\)

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(N < 10^4\)
  • Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input
5 100   
50 30 25    
50 40 25    
25 25 25    
75 20 25    
5 5 25 
Output
20

Bình luận

Không có bình luận nào.