# KOITST 22 Security System

https://www.acmicpc.net/problem/25023

The confidential facilities of the KOI nation can be represented as squares on the coordinate plane, with the bottom-left vertex at $(0,0)$ and the top-right vertex at $(N+1,N+1)$. Each side of the square represents a wall of the confidential facility.


Within the confidential facility, there are $N$ laser sensors. Each laser sensor is numbered from $0$ to $N-1$. A security system is designed to detect intruders in the confidential facility through these laser sensors.

Each laser sensor can be represented by a point on the coordinate plane. When a laser sensor is activated, it emits a beam in one of four directions: upwards ($+y$-axis direction), to the right ($+x$-axis direction), downwards ($-y$-axis direction), or to the left ($-x$-axis direction). The path of the laser beam until it reaches a wall can be represented by a line segment connecting the position of the laser sensor and a point on the wall.

The directions in which the laser beams are emitted are numbered from 1 to 4:

1 represents the upward direction,
2 represents the right direction,
3 represents the downward direction, and
4 represents the left direction.

The illustration below depicts examples of laser sensors emitting laser beams in directions 1, 2, 3, and 4 respectively. The black dots represent the laser sensors, and the red line segments represent the laser beams.


Each laser sensor, indexed from $0$ to $N-1$, is positioned at $(X[i], Y[i])$ and emits a beam in direction $D[i]$ when activated. Laser sensors are located at different positions, and $X[i]$ and $Y[i]$ are integers ranging from 1 to $N$.

You can choose the activation status of each laser sensor as desired. However, to avoid recognition errors caused by intersecting laser beams from different sensors, the laser beams must not intersect, including at their endpoints. The illustration below shows an example of intersecting laser beams, where the beams can intersect at a point or form line segments.


The importance of each laser sensor is represented by $W[i]$. Importance quantifies how much a sensor contributes to security when activated. The overall security level of the security system is the sum of the importance values of the activated laser sensors.

Determine the maximum possible security level when laser sensors are activated such that the laser beams do not intersect.

(translation: 0th, 1st, 2nd, 3rd sensor)

## Implementation

* $X$, $Y$, $D$, $W$: Arrays of length $N$ containing integers. For each $i$ $(0 \leq i \leq N-1)$, the coordinates of the $i$-th laser sensor are $(X[i], Y[i])$, it emits a beam in direction $D[i]$, and its importance is $W[i]$.
* The function should return the maximum possible security level when laser sensors are activated such that their beams do not intersect.

## Constraints:

* $1 \le N \le 1,500$
* $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$)
* Each sensor is located at a different position.

## Subtasks
![image](https://hackmd.io/_uploads/SJjuwpSMR.png)


## Example