Security System

The secret facility of the KOI country can be drawn as a square on the coordinate plane. The lower-left corner of the square is $(0,0)$, the upper-right corner is $(N+1,N+1)$, and its sides are parallel to the axes. Each side of the square is a wall of the facility.

The facility has $N$ laser sensors, numbered from $0$ to $N-1$. You are designing a security system that detects intruders with these laser sensors.

Each laser sensor is a point on the coordinate plane. When a sensor is activated, it fires a laser beam from its position in one of four directions: up (the $+y$ direction), right (the $+x$ direction), down (the $-y$ direction), or left (the $-x$ direction). The beam travels until it reaches a wall, so its path is the segment connecting the sensor and a point on the wall. The directions are numbered 1 to 4: 1 is up, 2 is right, 3 is down, and 4 is left. The figure below shows sensors firing in directions 1, 2, 3, and 4, in that order. Black dots are sensors and red segments are laser beams.

Sensor $i$ ($0 \le i \le N-1$) is at $(X[i], Y[i])$, and it fires in direction $D[i]$ when activated. Different sensors are at different positions. $X[i]$ and $Y[i]$ are integers from $1$ to $N$.

You can choose freely which sensors to activate. However, if beams from different sensors meet, the system may misread them, so no two beams may meet, including at their endpoints. The figure below shows beams meeting. Beams may meet at a single point or share a segment.

The importance of sensor $i$ ($0 \le i \le N-1$) is $W[i]$. Importance is a numeric measure of how much activating that sensor helps security. The security level of the whole system is the sum of the importance values of the activated sensors.

Write a function that returns the maximum possible security level, subject to choosing which sensors to activate so that no two laser beams meet.

$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 at a different position.