Vương quốc JOI có \(N\) ngôi nhà, đánh số từ \(1\) đến \(N\), nằm trên một đường thẳng theo thứ tự số hiệu. Mỗi nhà có một người dân; người sống trong nhà \(x\) (\(1 \le x \le N\)) được gọi là người dân \(x\).

Gần đây, một loại vi-rút mới xuất hiện và tất cả người dân đều bị nhiễm. Có \(M\) dự án điều trị được đề xuất. Dự án thứ \(i\) (\(1 \le i \le M\)) có chi phí \(C_i\). Nếu thực hiện dự án này thì vào buổi tối ngày thứ \(T_i\), mọi người dân \(x\) thỏa mãn \(L_i \le x \le R_i\) đang nhiễm vi-rút sẽ được chữa khỏi.

Vi-rút lây giữa các người dân ở nhà kề nhau như sau: nếu người dân \(x\) (\(1 \le x \le N\)) bị nhiễm vào buổi sáng của một ngày, thì đến buổi trưa cùng ngày, người dân \(x-1\) (nếu \(x \ge 2\)) và người dân \(x+1\) (nếu \(x \le N-1\)) sẽ bị nhiễm. Người đã được chữa khỏi vẫn có thể bị nhiễm lại.

Bạn là một bộ trưởng của vương quốc và phải chọn một số dự án sao cho sau khi tất cả dự án đã chọn được thực hiện, không còn người dân nào nhiễm vi-rút. Có thể thực hiện nhiều dự án trong cùng một ngày.

Cho số ngôi nhà và thông tin các dự án, hãy xác định có thể đạt được điều kiện trên hay không; nếu có, hãy tính tổng chi phí nhỏ nhất.

Dữ liệu vào

Đọc từ đầu vào chuẩn. Tất cả giá trị đều là số nguyên, theo định dạng:

N M
T_1 L_1 R_1 C_1
...
T_M L_M R_M C_M

Dữ liệu ra

In ra một dòng. Nếu không thể thỏa mãn điều kiện, in ra \(-1\); ngược lại, in ra tổng chi phí nhỏ nhất.

Ràng buộc

• \(1 \le N \le 1\,000\,000\,000\).
• \(1 \le M \le 100\,000\).
• \(1 \le T_i \le 1\,000\,000\,000\) với \(1 \le i \le M\).
• \(1 \le L_i \le R_i \le N\) với \(1 \le i \le M\).
• \(1 \le C_i \le 1\,000\,000\,000\) với \(1 \le i \le M\).

Phân nhóm

Các ràng buộc chung áp dụng cho mọi nhóm.

1. \(4\) điểm: \(T_i=1\) với mọi \(1 \le i \le M\)
2. \(5\) điểm: \(M \le 16\)
3. \(30\) điểm: \(M \le 5000\)
4. \(61\) điểm: Không có

Ví dụ

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

7

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

-1

10 5
1 5 10 4
1 1 6 5
1 4 8 3
1 6 10 3
1 1 3 1

7

Nguồn

JOI 2019/2020, Trại huấn luyện mùa xuân, ngày thi 4. Đề gốc của Ủy ban Olympic Tin học Nhật Bản, được cung cấp theo giấy phép CC BY-SA 4.0. Bản tiếng Việt được dịch từ đề tiếng Anh chính thức.