Background

Due to technical limitations, please do not use C++ 14 (GCC 9) to submit this problem.

This is an interactive problem. You only need to implement the function required in the code.

Your code does not need to include any additional header files, and you do not need to implement the main function.

Problem Description

Bu Dengklek has a catfish pond. The pond is a grid of $N \times N$ cells. Each cell is a square of the same size. The columns of the grid are numbered from west to east as $0$ to $N - 1$, and the rows are numbered from south to north as $0$ to $N - 1$. We denote the cell in column $c$ and row $r$ ($0 \le c \le N - 1$, $0 \le r \le N - 1$) as cell $(c, r)$.

There are $M$ catfish in the pond, numbered from $0$ to $M - 1$, and each is in a different cell. For each $i$ with $0 \le i \le M - 1$, catfish $i$ is in cell $(X_i, Y_i)$ and has weight $W_i$ grams.

Bu Dengklek wants to build some dikes to catch catfish. A dike of length $k$ in column $c$ (for all $0 \le c \le N - 1$ and $1 \le k \le N$) is a rectangle that goes from row $0$ up to row $k - 1$, covering cells $(c, 0), (c, 1), \ldots, (c, k - 1)$. For each column, Bu Dengklek may build a dike of some length of her choice, or build no dike.

Catfish $i$ (for all $0 \le i \le M - 1$) can be caught if there is a dike directly adjacent to its west side or east side, and there is no dike covering the cell it is in; that is, if:

• At least one of the cells $(X_i - 1, Y_i)$ or $(X_i + 1, Y_i)$ is covered by some dike, and
• No dike covers cell $(X_i, Y_i)$.

For example, consider a pond with $N = 5$ and $M = 4$ catfish:

• Catfish $0$ is in cell $(0, 2)$ and has weight $5$ grams.
• Catfish $1$ is in cell $(1, 1)$ and has weight $2$ grams.
• Catfish $2$ is in cell $(4, 4)$ and has weight $1$ gram.
• Catfish $3$ is in cell $(3, 3)$ and has weight $3$ grams.

Bu Dengklek can build dikes as follows:

Before building dikes	After building dikes

The number in a cell indicates the weight of the catfish in that cell.
Shaded cells are covered by dikes.
In this scenario, catfish $0$ (in cell $(0, 2)$) and catfish $3$ (in cell $(3, 3)$) can be caught.
Catfish $1$ (in cell $(1, 1)$) is not caught because a dike covers its cell. Catfish $2$ (in cell $(4, 4)$) is not caught because there is no dike directly adjacent to its west or east side.

Bu Dengklek wants to build dikes so that the total weight of caught catfish is as large as possible. Your task is to compute the maximum total weight of catfish that Bu Dengklek can catch by building dikes.

Input Format

You need to implement the following function:

int64 max_weights(int N, int M, int[] X, int[] Y, int[] W)

• $N$: the size of the pond.
• $M$: the number of catfish.
• $X$, $Y$: two arrays of length $M$ giving the positions of the catfish.
• $W$: an array of length $M$ giving the weights of the catfish.
• The function should return an integer representing the maximum total weight of catfish that Bu Dengklek can catch by building dikes.
• This function will be called exactly once.

Output Format

Consider the following call:

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

The explanation of this example can be found earlier in the statement.

After building the described dikes, Bu Dengklek can catch catfish $0$ and $3$, with total weight $5 + 3 = 8$ grams.
Since it is impossible to build dikes that catch catfish with total weight greater than $8$ grams, the function should return $8$.

Hint

Constraints

• $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$ (for all $0 \le i \le M - 1$)
• $1 \le W_i \le 10^9$ (for all $0 \le i \le M - 1$)
• No two catfish will be in the same cell.
  In other words, $X_i \neq X[j]$ or $Y_i \neq Y[j]$ (for all $0 \le i \lt j \le M - 1$).

Subtasks

1. (3 points) $X_i$ is even (for all $0 \le i \le M - 1$).
2. (6 points) $X_i \le 1$ (for all $0 \le i \le M - 1$).
3. (9 points) $Y_i = 0$ (for all $0 \le i \le M - 1$).
4. (14 points) $N \le 300$, $Y_i \le 8$ (for all $0 \le i \le M - 1$).
5. (21 points) $N \le 300$.
6. (17 points) $N \le 3000$.
7. (14 points) In each column, there are at most $2$ catfish.
8. (16 points) No additional constraints.

Sample grader

The sample grader reads input in the following format:

• Line $1$: $N \; M$
• Line $2 + i$ ($0 \le i \le M - 1$): $X_i \; Y_i \; W_i$

The sample grader prints your answer in the following format:

• Line $1$: the return value of max_weights.

Notes

In the statement, when giving the function interface, the following generic type names are used: void, int, int64, int[] (array), and int[][] (array of arrays).

In C++, the grader will use appropriate data types or implementations as shown in the following tables:

Translated by ChatGPT 5