Chọn Điểm Để Kích Hoạt Các Khoảng · canuc80k2641

Trên trục có $N$ vị trí đánh số từ $1$ đến $N$ . Bạn được chọn một tập vị trí bất kỳ, kể cả tập rỗng.

Có $M$ khoảng có trọng số. Khoảng thứ $i$ là $[l_{i}, r_{i}]$ và mang trọng số $a_{i}$ . Khoảng này đóng góp $a_{i}$ vào tổng điểm khi trong đoạn từ $l_{i}$ đến $r_{i}$ có ít nhất một vị trí được chọn; nếu không, nó đóng góp $0$ . Các khoảng được tính độc lập, kể cả khi chúng trùng nhau.

Hãy tìm điểm lớn nhất có thể đạt được.

Input

Dòng đầu chứa $N$ và $M$ .
Mỗi trong $M$ dòng tiếp theo chứa $l_{i}, r_{i}, a_{i}$ .

Output

In điểm lớn nhất.

Constraints

$1 \leq N, M \leq 2 \cdot 1 0^{5}$ .
$1 \leq l_{i} \leq r_{i} \leq N$ .
$∣ a_{i} ∣ \leq 1 0^{9}$ .

Scoring

Subtask $1$ ( $50%$ ): $N \leq 20, M \leq 25$ .
Subtask $2$ ( $50%$ ): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Chọn vị trí $2$ . Ba khoảng đầu được kích hoạt, còn khoảng $[3, 3]$ không được kích hoạt, nên điểm là $5 + 7 - 4 = 8$ . Không cách chọn nào đạt điểm lớn hơn.

Ý tưởng: Quét đầu phải của các khoảng từ trái sang phải. Trạng thái quan trọng không phải toàn bộ tập đã chọn, mà chỉ là vị trí được chọn cuối cùng.
Ý tưởng: Sau khi xử lý các khoảng có đầu phải không vượt quá i, đặt val[j] là điểm tốt nhất của một cấu hình mà vị trí chọn cuối cùng là j; j=0 biểu diễn chưa chọn vị trí nào.
Chuyển trạng thái: Trước khi xử lý các khoảng kết thúc tại i, ta có thể chọn vị trí i từ bất kỳ cấu hình cũ nào. Vì vậy gán
Chuyển trạng thái: val[i] = max_j val[j].
Chuyển trạng thái: Xét khoảng [l,i] có trọng số a. Khi đã quét tới i, khoảng này được kích hoạt khi và chỉ khi vị trí chọn cuối cùng j thỏa l≤j≤i. Do đó cần cộng a cho toàn bộ val[l..i].
Chuyển trạng thái: Ta cần ba phép toán:
Chuyển trạng thái: lấy maximum trên toàn bộ trạng thái;
Chuyển trạng thái: gán một điểm;
Chuyển trạng thái: cộng một giá trị trên một đoạn.
Chuyển trạng thái: Cây đoạn lazy hỗ trợ mỗi phép trong O(log N).
Chứng minh: Khi một khoảng kết thúc tại i, mọi vị trí đã chọn đều không vượt i; khoảng có ít nhất một vị trí chọn đúng khi vị trí chọn cuối cùng nằm từ l tới i. Vì vậy range-add cập nhật đúng và chỉ các cấu hình kích hoạt khoảng. Gán trạng thái i từ maximum toàn cục xét đầy đủ quyết định chọn i, còn các trạng thái cũ biểu diễn quyết định không chọn. Quy nạp theo i cho thấy cây đoạn lưu đúng giá trị tối ưu cho mỗi vị trí chọn cuối. Sau khi xử lý mọi khoảng, maximum toàn cục là điểm tối ưu; trạng thái 0 bảo đảm tập rỗng với điểm 0 luôn được xét.
Độ phức tạp: O((N+M)log N) thời gian và O(N+M) bộ nhớ.