Điều phối xe

Một đoàn gồm $m$ hành khách cần di chuyển qua $n$ chặng đường liên tiếp từ điểm xuất phát đến điểm đích.

Mỗi chặng đường $i$ ($1 ≤ i ≤ n$) có nhiệt độ môi trường là $t_i$ độ. Ban tổ chức sử dụng các xe khách để vận chuyển đoàn người. Khi một chiếc xe đi qua chặng $i$ và chở $k$ hành khách, nhiệt độ bên trong xe là $t_i + k$ độ.

Nếu nhiệt độ bên trong xe vượt quá ngưỡng $T_i$ độ tại chặng $i$, mỗi hành khách trên chiếc xe đó sẽ yêu cầu khoản tiền bồi hoàn là $x_i$ đồng vì điều kiện không thoải mái. Khoản bồi hoàn này được tính riêng tại mỗi chặng mà nhiệt độ trong xe vượt quá ngưỡng quy định.

Để tối ưu chi phí, ban tổ chức có thể tùy ý tăng hoặc giảm số lượng xe ở đầu chuyến đi cũng như giữa các chặng, miễn là luôn có ít nhất một xe hoạt động tại mỗi chặng. Ban tổ chức cũng có thể tùy ý phân chia các hành khách vào các xe mà không mất phí sắp xếp. Tuy nhiên, mỗi chiếc xe hoạt động tại chặng $i$ đều tốn chi phí thuê là $cost_i$ đồng.

Nhiệm vụ của bạn là tìm tổng chi phí nhỏ nhất tính bằng đồng mà ban tổ chức cần chi trả để đưa toàn bộ hành khách qua cả $n$ chặng đường.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($1 ≤ n ≤ 10^5$, $1 ≤ m ≤ 10^6$) lần lượt là số lượng chặng đường và số lượng hành khách trong đoàn.

Trong $n$ dòng tiếp theo, dòng thứ $i$ chứa bốn số nguyên $t_i$, $T_i$, $x_i$ và $cost_i$ ($1 ≤ t_i, T_i, x_i, cost_i ≤ 10^6$) cách nhau bởi dấu cách.

Kết quả

In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất mà ban tổ chức cần chi trả để đưa toàn bộ hành khách qua $n$ chặng đường.

Chấm điểm

Subtask 1 (20 points). $n ≤ 1500$; $m ≤ 2000$

Subtask 2 (30 points). Với mọi chặng i, hoặc $t_i ≥ T_i$ hoặc T_i - $t_i ≥ m$

Subtask 3 (50 points). $1 ≤ n ≤ 10^5$; $1 ≤ m ≤ 10^6$

Ví dụ

Input

2 10
30 35 1 100
20 35 10 10

Output

120

Ghi chú

Ở ví dụ trên, tại chặng thứ nhất, ban tổ chức chỉ sử dụng một xe. Khi đó nhiệt độ trong xe là $30 + 10 = 40$ độ, vượt quá ngưỡng $35$ độ nên mỗi hành khách trong số $10$ người đều nhận bồi hoàn $1$ đồng. Chi phí tại chặng này là $100 + 10 × 1 = 110$ đồng. Tại chặng thứ hai, ban tổ chức cũng chỉ dùng một xe và nhiệt độ trong xe là $20 + 10 = 30$ độ, không vượt quá ngưỡng $35$ độ nên chỉ tốn chi phí thuê xe là $10$ đồng. Tổng chi phí là $110 + 10 = 120$ đồng.