Bên cạnh Marathon, bạn Minh còn tham gia giải đua xe dọc theo \(OX\). Điểm xuất phát nằm tại điểm 0 và đích ở điểm \(L\) tức là cuộc đua có chiều dài \(L\) mét tính từ điểm xuất phát.

Bạn Minh luyện tập chăm chỉ đến mức có thể duy trì vận tốc 1 m/s (mét / giây). Bên cạnh đó trong cuộc đua còn có N đoạn dốc cất cánh được biểu thị bởi 4 đại lượng sau:

• \(x_i\) tọa độ của đoạn dốc.

• \(d_i\) quãng đường bay (tính theo mét, tức là chạm đất tại điểm \(x_i + d_i\)).

• \(t_i\) thời gian bay tính theo giây.

• \(p_i\) quãng đường lấy đà(tính theo mét, tức là phải ở mặt đất từ tọa độ \(x_i - p_i\)).

Bạn Minh được phép đi theo cả 2 hướng trên đường đua tức là có thể quay đầu lại nhưng cấm không được vượt quá điểm xuất phát và điểm đích đảm bảo \(x_i ≥ p_i\) và \(x_i + d_i ≤ L\). Mỗi con dốc có thể sử dụng bao nhiêu lần tùy ý (có thể là 0 tức bỏ qua con dốc đó).

Yêu cầu: Thời gian tối thiểu để Minh hoàn thành cuộc đua (Minh về tới đích).

Input

• Dòng 1: Số nguyên \(N, L ( N ≤ 200000, L ≤ 10^9)\) số đoạn dốc và chiều dài cuộc đua.

• \(N\) dòng tiếp theo mỗi dòng chứa 4 số \(x_i,d_i,t_i,p_i\) biểu thị con dốc thứ \(i\).

Output

• Ghi 1 số nguyên duy nhất là thời gian hoàn thành cuộc đua

Ràng buộc:

• Có 40% số test tương đương 40% số điểm có: \(N, L ≤ 2000\)

• Có 30% số test tương đương 30% số điểm có: \(p_i = 0\)

• Có 30% số test tương đương 30% số điểm không ràng buộc gì thêm

Sample Input

2 20
9 8 12 6
15 5 1 1

Sample Output

16