보안 시스템

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]$ 이다. 중요도는, 해당 레이저 센서를 작동시켰을 때 보안에 얼마나 도움이 되는지를 수치적으로 나타낸 값이다. 전체 보안 시스템의 보안 수준은 작동시킨 레이저 센서들의 중요도 값의 합이다.

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

보안 시스템

문제

제한