Hội thảo

Hội thảo khoa học về lĩnh vực trí tuệ nhân tạo có \(n\) đại biểu tham dự tại một hội trường lớn. Trong hội trường chỉ có \(m\) ghế, do đó tại mỗi thời điểm có không quá \(m\) người được ngồi. Với đại biểu thứ \(i\) (\(1 \le i \le n\)) cho biết các thông tin sau:

• Người thứ \(i\) có mặt từ thời điểm \(s_i\) đến thời điểm \(f_i\);

• Nếu người \(i\) ngồi ghế trong một đơn vị thời gian thì mức độ nhiệt tình đóng góp ý kiến trong đơn vị thời gian ngồi đó là \(a_i\), còn nếu đứng thì mức độ nhiệt tình đóng góp ý kiến trong đơn vị thời gian đứng là \(b_i\). Tuy nhiên, có thể có người lại thích đứng hơn thích ngồi dù còn thừa ghế (\(a_i < b_i\)).

Yêu cầu: Cho thông tin về \(n\) người tham dự hội thảo và số ghế \(m\) có trong hội trường, hỏi tổng mức độ nhiệt tình tham gia đóng góp ý kiến lớn nhất là bao nhiêu?

Input

Dữ liệu vào có dạng:

• Dòng thứ nhất chứa hai số nguyên dương \(n, m\) (\(1 \le n, m \le 10^5\));

• Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa bốn số nguyên \(a_i, b_i, s_i, f_i\) (\(|a_i|, |b_i| \le 10^9\); \(0 < s_i < f_i < 10^9\)).
  Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách. Dữ liệu vào đảm bảo kết quả bài toán không vượt quá giá trị \(10^{18}\).

Người \(i\) có mặt trong khoảng thời gian \([s_i, f_i)\), tức là gồm \(f_i - s_i\) đơn vị thời gian, trong mỗi đơn vị người đó hoặc ngồi hoặc đứng.

Ràng buộc:

• Có \(10\%\) số test ứng với \(10\%\) số điểm có giá trị \(n = 1\);

• Có \(10\%\) số test ứng với \(10\%\) số điểm có giá trị \(n = 2\);

• Có \(20\%\) số test ứng với \(20\%\) số điểm có giá trị \(n \le 100\);

• Có \(60\%\) số test ứng với \(60\%\) số điểm có giá trị \(n \le 10^5\).

Output

In ra một dòng chứa một số nguyên duy nhất là tổng mức độ nhiệt tình tham gia đóng góp ý kiến lớn nhất có thể.

Example

Input:

4 2
10 -10 2 3
-1 -3 1 4
6 -6 1 3
7 4 2 4

Output:

28

Note

• Người \(1\) ngồi ghế từ thời điểm \(2\) đến thời điểm \(3\), đóng góp: \(10\).

• Người \(2\) ngồi ghế từ thời điểm \(1\) đến thời điểm \(2\), đứng từ thời điểm \(2\) đến thời điểm \(3\), ngồi ghế từ thời điểm \(3\) đến thời điểm \(4\), đóng góp: \(-1 + (-3) + (-1) = -5\).

• Người \(3\) ngồi ghế từ thời điểm \(1\) đến thời điểm \(3\), đóng góp: \(6 + 6 = 12\).

• Người \(4\) đứng từ thời điểm \(2\) đến thời điểm \(3\), ngồi ghế từ thời điểm \(3\) đến thời điểm \(4\), đóng góp: \(4 + 7 = 11\).
  Tổng mức độ nhiệt tình tham gia là: \(10 + (-5) + 12 + 11 = 28\).