보안 시스템

KOI국의 기밀 시설은 좌표평면 위의 정사각형으로 나타낼 수 있다. 정사각형의 왼쪽 아래 꼭짓점은 $(0,0)$이고, 오른쪽 위 꼭짓점은 $(N+1,N+1)$이다. 네 변은 축에 평행하며, 정사각형의 각 변이 기밀 시설의 벽이다.

기밀 시설 안에는 $N$개의 레이저 센서가 있다. 센서에는 $0$부터 $N-1$까지 번호가 붙어 있다. 레이저 센서로 침입자를 감지하는 보안 시스템을 설계하려고 한다.

각 레이저 센서는 좌표평면 위의 한 점이다. 센서를 작동시키면 그 위치에서 위쪽($+y$축 방향), 오른쪽($+x$축 방향), 아래쪽($-y$축 방향), 왼쪽($-x$축 방향) 중 한 방향으로 레이저 빛을 발사한다. 레이저 빛은 벽에 닿을 때까지 나아가므로, 빛의 경로는 센서 위치와 벽 위의 한 점을 잇는 선분이다. 발사 방향은 1부터 4까지 번호로 나타낸다. 1은 위쪽, 2는 오른쪽, 3은 아래쪽, 4는 왼쪽이다. 아래 그림은 1번, 2번, 3번, 4번 방향으로 빛을 발사하는 센서의 예이다. 검은 점은 레이저 센서이고, 빨간 선분은 레이저 빛이다.

$i$번 레이저 센서($0 \le i \le N-1$)는 $(X[i], Y[i])$에 놓여 있고, 작동시키면 $D[i]$번 방향으로 빛을 발사한다. 서로 다른 센서는 서로 다른 위치에 놓여 있다. $X[i]$와 $Y[i]$는 $1$ 이상 $N$ 이하의 정수이다.

각 센서의 작동 여부는 원하는 대로 정할 수 있다. 다만 서로 다른 센서가 쏜 레이저 빛이 만나면 인식 오류가 생길 수 있으므로, 레이저 빛들은 끝 점을 포함해서 서로 만나지 않아야 한다. 아래 그림은 레이저 빛이 만나는 예이다. 빛끼리는 한 점에서 만날 수도 있고, 선분으로 겹칠 수도 있다.

$i$번 레이저 센서($0 \le i \le N-1$)의 중요도는 $W[i]$이다. 중요도는 그 센서를 작동시켰을 때 보안에 얼마나 도움이 되는지를 수치로 나타낸 값이다. 보안 시스템 전체의 보안 수준은 작동시킨 센서들의 중요도 합이다.

레이저 빛끼리 만나지 않도록 센서들의 작동 여부를 정했을 때, 가능한 보안 수준의 최댓값을 구하는 함수를 작성하라.

$1 \le N \le 1\,500$

$1 \le X[i], Y[i] \le N$ (모든 $0 \le i \le N-1$)

$D[i] \in \{1, 2, 3, 4\}$ (모든 $0 \le i \le N-1$)

$1 \le W[i] \le 100\,000$ (모든 $0 \le i \le N-1$)

각 센서는 모두 서로 다른 위치에 있다.