Bu Dengklek sở hữu một trang trại nuôi cá da trơn.
Trang trại cá da trơn là một ao bao gồm một lưới \(N \times N\) ô vuông.
Mỗi ô là một hình vuông cùng kích thước.
Các cột của lưới được đánh số từ \(0\) đến \(N - 1\) từ tây sang đông và các hàng được đánh số từ \(0\) đến \(N - 1\) từ nam sang bắc.
Gọi ô nằm ở cột \(c\) và hàng \(r\) của lưới (\(0 \le c \le N - 1\), \(0 \le r \le N - 1\)) là ô \((c, r)\).

Trong ao có \(M\) con cá da trơn, được đánh số từ \(0\) đến \(M - 1\), nằm ở các ô riêng biệt.
Với mỗi \(i\) mà \(0 \le i \le M - 1\), con cá \(i\) nằm ở ô \((X[i], Y[i])\) và nặng \(W[i]\) gam.

Bu Dengklek muốn xây một số cầu để bắt cá da trơn.
Một cầu trong cột \(c\) có chiều dài \(k\) (với mọi \(0 \le c \le N - 1\) và \(1 \le k \le N\)) là một hình chữ nhật kéo dài từ hàng \(0\) đến hàng \(k - 1\), bao gồm các ô \((c, 0), (c, 1), \ldots, (c, k - 1)\).
Đối với mỗi cột, Bu Dengklek có thể chọn xây cầu có độ dài theo ý mình hoặc không xây cầu.

Con cá \(i\) (với mỗi \(i\) sao cho \(0 \le i \le M - 1\)) có thể đánh bắt được nếu có cầu ngay sát phía tây hoặc phía đông ô của nó và không có cầu che ô của nó; nghĩa là, nếu

• ít nhất một trong số các ô \((X[i] - 1, Y[i])\) hoặc \((X[i] + 1, Y[i])\) được che bởi một cầu, và
• không có cầu che ô \((X[i], Y[i])\).

Ví dụ, xét một ao có kích thước \(N = 5\) với \(M = 4\) con cá da trơn:

• Con cá \(0\) nằm ở ô \((0, 2)\) và nặng \(5\) gam.
• Con cá \(1\) nằm ở ô \((1, 1)\) và nặng \(2\) gam.
• Con cá \(2\) nằm ở ô \((4, 4)\) và nặng \(1\) gam.
• Con cá \(3\) nằm ở ô \((3, 3)\) và nặng \(3\) gam.

Sau đây là một cách Bu Dengklek có thể xây dựng các cầu:

Trước khi các cầu được xây dựng	Sau khi các cầu được xây dựng

Con số trong một ô chỉ trọng lượng của con cá da trơn ở ô đó.
Các ô tô đậm là các ô được che bởi các cầu.
Trong trường hợp này, có thể đánh bắt được con cá da trơn \(0\) (tại ô \((0, 2)\)) và con cá da trơn \(3\) (tại ô \((3, 3)\)).
Không thể đánh bắt được con cá da trơn \(1\) (tại ô \((1, 1)\)) vì có một cầu che vị trí của nó, trong khi không thể đánh bắt được con cá da trơn \(2\) (tại ô \((4, 4)\)) vì không có cầu ngay sát phía tây và phía đông ô của nó.

Bu Dengklek muốn xây các cầu sao cho tổng trọng lượng các cá da trơn mà cô có thể bắt được càng lớn càng tốt.
Nhiệm vụ của bạn là tìm tổng trọng lượng lớn nhất các cá da trơn mà Bu Dengklek có thể bắt được sau khi xây các cầu.

Chi tiết cài đặt

Bạn cần cài đặt các hàm sau:

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W);

• \(N\): kích thước của ao.
• \(M\): số lượng cá da trơn.
• \(X\), \(Y\): các mảng \(M\) phần tử mô tả các vị trí cá da trơn.
• \(W\): mảng \(M\) phần tử chứa trọng lượng các cá da trơn.
• Hàm này cần trả về một số nguyên biểu diễn tổng trọng lượng lớn nhất các cá da trơn mà Bu Dengklek có thể bắt được sau khi xây các cầu.
• Hàm này được gọi đúng một lần.

Ví dụ

Xét lời gọi hàm sau:

max_weights(5, 4, [0, 1, 4, 3], [2, 1, 4, 3], [5, 2, 1, 3])

Ví dụ này được minh hoạ trong phần mô tả bài toán ở trên.

Sau khi xây dựng các cầu như mô tả, Bu Dengklek có thể đánh bắt được con cá \(0\) và \(3\), có tổng trọng lượng là \(5 + 3 = 8\) gam.
Vì không có cách nào xây các cầu để bắt các cá da trơn với tổng trọng lượng lớn hơn \(8\) gam, hàm cần trả về \(8\).

Ràng buộc

• \(2 \le N \le 100\;000\)
• \(1 \le M \le 300\;000\)
• \(0 \le X[i] \le N - 1\), \(0 \le Y[i] \le N - 1\) (với mỗi \(i\) sao cho \(0 \le i \le M - 1\))
• \(1 \le W[i] \le 10^9\) (với mỗi \(i\) sao cho \(0 \le i \le M - 1\))
• Không có hai con cá da trơn nào ở chung một ô.
  Nói cách khác, \(X[i] \neq X[j]\) hoặc \(Y[i] \neq Y[j]\) (với mỗi \(i\) và \(j\) sao cho \(0 \le i < j \le M - 1\)).

Phân nhóm

1. (3 điểm) \(X[i]\) là chẵn (với mỗi \(i\) sao cho \(0 \le i \le M - 1\))
2. (6 điểm) \(X[i] \le 1\) (với mỗi \(i\) sao cho \(0 \le i \le M - 1\))
3. (9 điểm) \(Y[i] = 0\) (với mỗi \(i\) sao cho \(0 \le i \le M - 1\))
4. (14 điểm) \(N \le 300\), \(Y[i] \le 8\) (với mỗi \(i\) sao cho \(0 \le i \le M - 1\))
5. (21 điểm) \(N \le 300\)
6. (17 điểm) \(N \le 3000\)
7. (14 điểm) Có tối đa \(2\) con cá da trơn mỗi cột.
8. (16 điểm) Không có ràng buộc gì thêm.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

• dòng \(1\): \(N \; M\)
• dòng \(2 + i\) (\(0 \le i \le M - 1\)): \(X[i] \; Y[i] \; W[i]\)

Trình chấm mẫu in ra câu trả lời của bạn theo định dạng sau:

• dòng \(1\): giá trị trả về của max_weights

Nguồn: Đề thi tiếng Việt IOI 2022, giấy phép CC-BY.