A confidential facility in the KOI country can be represented on a coordinate plane as a square with its bottom-left corner at $(0, 0)$ and its top-right corner at $(N + 1, N + 1)$, with sides parallel to the axes. Each edge of the square represents a wall of the confidential facility.

There are $N$ laser sensors inside the confidential facility. The laser sensors are numbered from $0$ to $N - 1$. We intend to design a security system that detects intruders in the confidential facility using these laser sensors.

Each laser sensor can be represented as a point on the coordinate plane. When a laser sensor is activated, it fires a laser beam from its position in one of four directions: upward (positive $y$-axis direction), rightward (positive $x$-axis direction), downward (negative $y$-axis direction), or leftward (negative $x$-axis direction). Since the laser beam travels until it reaches a wall, the path of the laser beam can be represented as a line segment connecting the position of the laser sensor to a point on the wall.

The directions in which the laser beam is fired are numbered from $1$ to $4$. $1$ represents the upward direction, $2$ represents the rightward direction, $3$ represents the downward direction, and $4$ represents the leftward direction. The figures below show examples of laser sensors firing laser beams in directions $1, 2, 3,$ and $4$, respectively. Black dots represent laser sensors, and red line segments represent laser beams.

The $i$-th laser sensor ($0 \le i \le N - 1$) is located at $(X[i], Y[i])$, and when activated, it fires a beam in the direction $D[i]$. Different laser sensors are located at different positions. $X[i]$ and $Y[i]$ are integers between $1$ and $N$, inclusive.

You can decide whether to activate each laser sensor. However, since an recognition error may occur if laser beams fired by different laser sensors meet, you must ensure that the laser beams do not meet each other, including their endpoints. The figure below shows examples of laser beams meeting; laser beams can meet at a single point or along a line segment.

The importance of the $i$-th laser sensor ($0 \le i \le N - 1$) is $W[i]$. The importance is a numerical value representing how much the sensor contributes to security when activated. The security level of the entire security system is the sum of the importance values of the activated laser sensors.

Write a function that calculates the maximum possible security level when deciding whether to activate each laser sensor such that the laser beams do not meet each other.

Implementation Details

You must implement the following function:

int max_level(vector<int> X, vector<int> Y, vector<int> D, vector<int> W)

• $X, Y, D, W$: Integer arrays of length $N$. For every $i$ ($0 \le i \le N - 1$), the $i$-th laser sensor is at $(X[i], Y[i])$, fires a beam in direction $D[i]$ when activated, and has importance $W[i]$.
• This function should return the maximum possible security level when deciding whether to activate each laser sensor such that the laser beams do not meet each other.

You must not execute input/output functions in any part of the submitted source code.

Examples

Consider the case where $N = 4, X = [1, 2, 3, 4], Y = [1, 2, 3, 4], D = [1, 1, 4, 4], W = [1, 1, 1, 1]$. The grader calls the function as follows:

max_level({1, 2, 3, 4}, {1, 2, 3, 4}, {1, 1, 4, 4}, {1, 1, 1, 1})

The figure below shows the confidential facility, the sensors inside, and the laser beams fired by the sensors. Activating sensor $0$ and sensor $1$, or activating sensor $2$ and sensor $3$, results in a security level of $2$ without the laser beams meeting. There is no way to achieve a higher security level than these two methods.

Therefore, the function should return $2$.

Constraints

• $1 \le N \le 1500$
• $1 \le X[i], Y[i] \le N$ (for all $0 \le i \le N - 1$)
• $D[i] \in \{1, 2, 3, 4\}$ (for all $0 \le i \le N - 1$)
• $1 \le W[i] \le 100\,000$ (for all $0 \le i \le N - 1$)
• All sensors are located at distinct positions.

Subtasks

1. (5 points) $N \le 18$
2. (8 points) $N \le 36$
3. (21 points) $N \le 100$
4. (15 points) $N \le 500$
5. (11 points) $D[i] \in \{1, 2, 3\}$ (for all $0 \le i \le N - 1$)
6. (17 points) $X[i] \neq X[j]$ and $Y[i] \neq Y[j]$ (for all $0 \le i < j \le N - 1$)
7. (23 points) No additional constraints

Note

The input format for the sample grader is as follows:

• Line 1: $N$
• Line $2 + i$ ($0 \le i \le N - 1$): $X[i] \ Y[i] \ D[i] \ W[i]$

The output format for the sample grader is as follows:

• Line 1: The value returned by the max_level function

Note that the sample grader may differ from the grader used in actual evaluation.