Bàn pinball là một lưới gồm \(M+2\) hàng và \(N\) cột. Hàng thứ nhất là đỉnh bàn và hàng thứ \(M+2\) là đáy bàn. Ô tại hàng \(i\), cột \(j\) được ký hiệu là \((i,j)\).

Một quả bóng xuất hiện tại một ô bất kỳ trên hàng đầu tiên rồi rơi thẳng xuống. Nếu bóng xuất hiện tại \((1,i)\) và không gặp thiết bị nào, nó sẽ đi qua các ô \((2,i),\ldots,(M+1,i)\) rồi đến \((M+2,i)\).

Có \(M\) thiết bị, đánh số từ \(1\) đến \(M\). Thiết bị \(i\) nằm trên hàng \(i+1\), phủ các ô từ \((i+1,A_i)\) đến \((i+1,B_i)\). Khi bóng chạm một ô thuộc thiết bị này, bóng được chuyển đến ô \((i+1,C_i)\) rồi tiếp tục rơi dọc theo cột \(C_i\). Mỗi thiết bị tương tác với một quả bóng không quá một lần.

Đặt thiết bị \(i\) lên bàn tốn \(D_i\) yên. Alice muốn chọn một số thiết bị sao cho dù bóng xuất hiện ở ô nào trên hàng đầu tiên, nó chỉ có thể đến đúng một ô duy nhất ở hàng đáy. Hãy tìm tổng chi phí nhỏ nhất.

Dữ liệu vào

• Dòng đầu gồm \(M,N\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) gồm \(A_i,B_i,C_i,D_i\).

Dữ liệu ra

In tổng chi phí nhỏ nhất để chỉ còn một ô ở hàng đáy mà bóng có thể đến. Nếu không thể, in -1.

Ràng buộc

• \(1 \le M \le 100\,000\).
• \(2 \le N \le 1\,000\,000\,000\).
• \(1 \le A_i \le C_i \le B_i \le N\).
• \(1 \le D_i \le 1\,000\,000\,000\).

Phân nhóm

• Nhóm 1 (11 điểm): \(M \le 10\), \(N \le 1\,000\)
• Nhóm 2 (18 điểm): \(M \le 200\)
• Nhóm 3 (22 điểm): \(M \le 1\,000\)
• Nhóm 4 (49 điểm): Không có ràng buộc bổ sung

Ví dụ

5 6
2 4 3 5
1 2 2 8
3 6 5 2
4 6 4 7
2 4 3 10

25

3 5
2 4 3 10
1 3 1 20
2 5 4 30

-1