에너지 생성

입자 충돌 에너지 생성기가 주어진다. 이 생성기는 $N$개의 타워가 놓인 2차원 평면이다. $i$번째 타워는 $(X_i, Y_i)$에 있고, 모든 타워의 영향 범위 반지름은 $R$로 같다.

각 타워는 고정된 배치로 네 종류의 입자를 방출한다. 타워는 입자 A, B, C, D를 시계 방향 순서대로, x축과 y축으로 나뉘는 각 사분면마다 하나씩 방출한다. 타워는 x축과 y축 위에서는 입자를 방출하지 않는다.

처음에 각 타워는 90도의 배수 각도로 놓여 있다. 위 오른쪽, 아래 오른쪽, 아래 왼쪽, 위 왼쪽 사분면에서 방출되는 입자를 차례로 적으면 다음과 같다.

• 0도: (A, B, C, D). 그림과 같다.
• 90도 (0도에서 시계 방향으로 회전): (D, A, B, C)
• 180도: (C, D, A, B)
• 270도: (B, C, D, A)

타워 $i$와 타워 $j$ 사이에 다음 조건이 모두 성립하면 흥미로운 현상이 일어날 수 있다.

1. $X_i \neq X_j$
2. $Y_i \neq Y_j$
3. 두 타워 사이의 유클리드 거리가 $R$ 이하이다.

타워 $i$가 타워 $j$가 있는 사분면에 방출하는 입자를 $p$, 타워 $j$가 타워 $i$가 있는 사분면에 방출하는 입자를 $q$라고 하자. 서로 마주 보는 면에서 방출되는 입자의 쌍 $\langle p, q\rangle$를 마주 보는 입자 쌍이라고 한다.

• $\langle A, C\rangle$, $\langle C, A\rangle$, $\langle B, D\rangle$, $\langle D, B\rangle$이면 타워 $i$는 $G$의 상호작용 에너지를 생성한다.
• $\langle A, A\rangle$, $\langle B, B\rangle$, $\langle C, C\rangle$, $\langle D, D\rangle$이면 타워 $i$는 $-G$를 생성한다. 즉 $G$의 에너지를 소모한다.
• 나머지 8가지 조합이면 두 타워는 상호작용하지 않으며, 이 쌍에서는 에너지가 생기지 않는다.

이 현상은 각 타워의 관점에서 양쪽 모두에 적용된다. 조건을 만족하는 쌍마다 효과가 더해진다.

두 타워 사이에서 생성되는 에너지의 예는 아래 표와 같다.

<A, C>를 방출	<D, D>를 방출	<B, C>를 방출	$X_1 = X_2$
각 타워가 +$G$ 에너지를 생성	각 타워가 -$G$ 에너지를 생성	두 타워 사이에 상호작용이 없음	이 두 타워 사이에서는 흥미로운 현상이 일어나지 않음

각 타워는 초기 방향에서 스스로 $P$의 에너지를 생성한다. 어느 방향으로든 90도 회전할 때마다 그 타워의 자체 에너지는 $P$만큼 줄어든다. 90도 회전한 타워는 자체 에너지가 0이고, 180도 회전한 타워는 $-P$를 생성한다. 타워는 90도의 배수만큼만 회전할 수 있다.

0개 이상의 타워 방향을 바꿔서 얻을 수 있는 총 에너지의 최댓값을 구하라. 한 배치의 총 에너지는 각 타워의 자체 에너지와 모든 조건 만족 쌍의 상호작용 에너지를 더한 값이다.

첫 줄에 정수 $N$, $R$, $G$, $P$가 주어진다 ($1 \le N \le 50$, $1 \le R, G, P \le 1000$). 각각 타워의 개수, 영향 범위의 반지름, 상호작용 에너지 상수, 각 타워가 초기에 자체로 생성하는 에너지이다. 다음 $N$개 줄에는 정수 $X_i$, $Y_i$, $O_i$가 주어진다 ($-1000 \le X_i, Y_i \le 1000$, $O_i \in \{0, 90, 180, 270\}$). $X_i$, $Y_i$는 $i$번째 타워의 위치이고 $O_i$는 초기 방향이다. 같은 위치에 있는 두 타워는 없다.

모든 타워 방향 배치 중에서 얻을 수 있는 총 에너지의 최댓값을 한 줄에 정수로 출력한다.