Energy Generation

You are given a particle collision energy generator. The generator is a two-dimensional field with $N$ towers. The $i$th tower is located at $(X_i, Y_i)$, and all towers have the same field of effect with a radius of $R$.

Each tower radiates four types of particles in a fixed configuration. Each tower radiates particles A, B, C, and D in clockwise order, one on each quadrant (an area separated by its x-axis and y-axis). A tower does not radiate any particle on its x-axis or y-axis.

Initially, each tower is oriented at a multiple of 90 degrees. The particles on the upper right, lower right, lower left, and upper left quadrants are listed in that order.

• 0 degrees: (A, B, C, D), as shown in the figure.
• 90 degrees (rotated clockwise from 0): (D, A, B, C).
• 180 degrees: (C, D, A, B).
• 270 degrees: (B, C, D, A).

An interesting phenomenon can occur between tower $i$ and tower $j$ when all of the following hold:

1. $X_i \neq X_j$
2. $Y_i \neq Y_j$
3. The Euclidean distance between them is at most $R$.

Let $p$ be the particle that tower $i$ radiates on the quadrant where tower $j$ is located, and let $q$ be the particle that tower $j$ radiates on the quadrant where tower $i$ is located. The pair $\langle p, q\rangle$ is the pair of facing particles.

• If the pair is $\langle A, C\rangle$, $\langle C, A\rangle$, $\langle B, D\rangle$, or $\langle D, B\rangle$, tower $i$ generates interaction energy of $G$.
• If the pair is $\langle A, A\rangle$, $\langle B, B\rangle$, $\langle C, C\rangle$, or $\langle D, D\rangle$, tower $i$ generates $-G$, which means it consumes $G$ energy.
• For the other 8 combinations, the two towers do not interact and no energy comes from this pair.

The phenomenon applies from each tower's perspective. Every qualifying pair adds its effect, so the effects stack.

Examples of the energy generated by a pair of towers are shown below.

Radiates <A, C>	Radiates <D, D>	Radiates <B, C>	$X_1 = X_2$
Each tower generates +$G$ energy	Each tower generates -$G$ energy	No interaction between these towers	No interesting phenomenon occurs between these towers

Each tower also generates $P$ energy by itself at its initial orientation. Each 90 degree rotation in either direction reduces that passive energy by $P$. A tower rotated 90 degrees produces 0 passive energy, and a tower rotated 180 degrees produces $-P$. A tower can be rotated only by multiples of 90 degrees.

Find the maximum total energy that can be generated by changing the orientation of zero or more towers. The total energy of a configuration is the sum of each tower's passive energy and the interaction energy from all qualifying pairs.

The first line contains four integers $N$, $R$, $G$, and $P$ ($1 \le N \le 50$, $1 \le R, G, P \le 1000$), the number of towers, the radius of effect, the interaction energy constant, and the initial passive energy of each tower. Each of the next $N$ lines contains three integers $X_i$, $Y_i$, and $O_i$ ($-1000 \le X_i, Y_i \le 1000$, $O_i \in \{0, 90, 180, 270\}$), the position and initial orientation of the $i$th tower. No two towers share the same position.

Print one integer on a line, the maximum total energy over all possible orientation configurations of the towers.