Ngày Nóng

Một tuyến đường đi qua $n$ vùng nối tiếp nhau. Vùng thứ $i$ có nhiệt độ ổn định $t_i$ độ.

Một nhóm gồm $m$ học sinh cần đi qua toàn bộ $n$ vùng bằng xe buýt. Khi một chiếc xe buýt chở $k$ học sinh đi qua vùng thứ $i$, nhiệt độ bên trong xe là $t_i+k$ độ. Nếu nhiệt độ bên trong xe vượt quá $T_i$ độ (tức là $t_i+k>T_i$), thì mỗi học sinh ngồi trong xe đó đòi bồi thường $x_i$ đồng cho vùng đó.

Ban tổ chức có thể tùy ý thêm hoặc bớt xe buýt tại điểm đầu và giữa mỗi cặp vùng liền kề (nhưng để đi qua một vùng thì cần ít nhất một xe), và có thể sắp xếp học sinh vào các xe một cách tùy ý (việc sắp xếp không tốn chi phí). Mỗi chiếc xe buýt được dùng để đi qua vùng thứ $i$ tốn $cos{t}_i$ đồng.

Hãy tính tổng số tiền nhỏ nhất mà ban tổ chức phải chi để đưa toàn bộ học sinh đi qua tất cả các vùng.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa bốn số nguyên $t_i$, $T_i$, $x_i$, $cos{t}_i$.

Dữ liệu ra

• In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le m\le {10}^6$
• $1\le t_i,T_i,x_i,cos{t}_i\le {10}^6$

Ví dụ