题目描述

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 position $(X_i, Y_i)$, and all towers have the same field of effect with a radius of $R$. Each tower radiates $4$ types of particles at a fixed configuration. Specifically, each tower radiates each particle $A$, $B$, $C$, and $D$ on its own quadrant (area separated by both its x-axis and y-axis) in a clockwise order, respectively. The tower does not radiate any particle at its x-axis or y-axis.

Initially, each tower is oriented at a multiple of $90^\circ$ angle. Let $(\cdot, \cdot, \cdot, \cdot)$ represents the particles radiated by a tower on its upper right, lower right, lower left, and upper left quadrant, respectively.

• If the tower is oriented at $0^\circ$, then it radiates $(A, B, C, D)$ as illustrated in the figure on the right.
• If the tower is oriented at $90^\circ$ (rotated clockwise from $0^\circ$), then it radiates $(D, A, B, C)$.
• If the tower is oriented at $180^\circ$, then it radiates $(C, D, A, B)$.
• If the tower is oriented at $270^\circ$, then it radiates $(B, C, D, A)$.

:::align{center} :::

An interesting phenomenon might occur on the $i^{th}$ tower when there is a $j^{th}$ tower such that the following conditions are satisfied.

1. $X_i \neq X_j$,
2. $Y_i \neq Y_j$, and
3. their Euclidean distance is no larger than $R$.

The interesting phenomenon is as follow. Let $p$ be the particle that is radiated by the $i^{th}$ tower on the quadrant where the $j^{th}$ tower is located, and $q$ be the particle that is radiated by the $j^{th}$ tower on the quadrant where the $i^{th}$ tower is located. For simplicity, let's say $\langle p, q \rangle$ are the particles radiated by their facing sides.

• If their facing sides are radiating either $\langle A, C \rangle$, $\langle C, A \rangle$, $\langle B, D \rangle$, or $\langle D, B \rangle$, then the $i^{th}$ tower will generate an interaction energy of $G$.
• If their facing sides are radiating the same particles, $\langle A, A \rangle$, $\langle B, B \rangle$, $\langle C, C \rangle$, or $\langle D, D \rangle$, then the $i^{th}$ tower will generate an interaction energy of $-G$; in other words, it consumes $G$ energy.
• If their facing sides are radiating any one of the remaining $8$ possible combination of particles that are not mentioned above, then the $i^{th}$ tower is not interacting with the $j^{th}$ tower. In other words, there is no energy generated from this pair of towers.

This phenomenon applies both ways (from each tower's perspective) and stacks indefinitely if there are multiple towers satisfying the conditions.

Here are some examples of the energy generated from a pair of towers.

:::align{center} :::

Each tower also passively generates its own energy. Initially, each tower generates $P$ energy by itself.

You have the option to change the orientation of each tower by rotating it, possibly taking advantage of the interesting phenomenon and increasing the total amount of energy generated. Each $90^\circ$ rotation in any direction (either CW/clockwise or CCW/counterclockwise) causes the tower to produce $P$ less energy passively. A tower that is rotated $90^\circ$ in any direction will produce $0$ energy passively and a tower that is rotated $180^\circ$ (rotated $90^\circ$ twice in the same direction) will produce $-P$ energy (or in other words, consume $P$ energy). Note that you can only rotate any tower by a multiple of $90^\circ$.

Your task in this problem is to find the maximum amount of total energy that can be generated by changing the orientation of zero or more towers in any way. The total energy generated in a configuration is the sum of energy generated by each tower either passively or due to interaction with another tower in the configuration.

输入格式

Input begins with a line containing $4$ integers $N$ $R$ $G$ $P$ ($1 \leq N \leq 50$; $1 \leq R, G, P \leq 1000$) representing the number of towers, the radius of effect of all towers, the tower interaction energy constant, and the initial energy passively generated by each tower, respectively. The following $N$ lines contain $3$ integers $X_i$ $Y_i$ $O_i$ ($-1000 \leq X_i, Y_i \leq 1000$; $O_i \in \{0, 90, 180, 270\}$) representing the position and the initial orientation of the $i^{th}$ tower. It is guaranteed that no two towers have the same position.

输出格式

Output contains an integer in a line representing the maximum amount of total energy that can be generated out of all possible configurations of the towers.

3 10 10 15
0 0 0
2 2 180
100 100 180

35

3 10 1 1000
0 0 0
2 2 0
-4 4 180

2998

4 10 1000 1
0 0 0
0 2 90
2 0 180
2 2 270

4002

提示

Explanation for the sample input/output #1

The maximum amount of total generated energy can be obtained by rotating the $2^{nd}$ tower for $180^\circ$. No interesting phenomenon can happen on the $3^{th}$ tower as its Euclidean distance to any other towers is larger than $R$. By not rotating the $3^{th}$ tower, it generates $15$ passive energy. Rotating the $2^{nd}$ tower for $180^\circ$ will cause it to be oriented at $0^\circ$. An interesting phenomenon occurs on the $1^{st}$ tower and the $2^{nd}$ tower as they satisfy all the conditions and their facing side radiates $\langle A, C \rangle$ (or $\langle C, A \rangle$ from the $2^{nd}$ tower's perspective). The $1^{st}$ tower will produce $15 + 10 = 25$ from its passive energy generation and interaction with the $2^{nd}$ tower, while the $2^{nd}$ tower will produce $-15 + 10 = -5$ energy. These $3$ towers generate a total energy of $25 - 5 + 15 = 35$ in this configuration.

Explanation for the sample input/output #2

The maximum amount of total generated energy can be obtained by not doing any rotation. These $3$ towers are interacting with each other at their current orientation. The $1^{st}$ and $2^{nd}$ towers each generates $1 + (-1) = 0$ interaction energy while the $3^{rd}$ tower generates $-1 + (-1) = -2$ interaction energy. Each tower also passively generates $1000$ energy. The total energy generated in this configuration is $2998$.

Explanation for the sample input/output #3

The maximum amount of total generated energy can be obtained by rotating the $1^{st}$ tower for $90^\circ$ CCW and the $2^{nd}$ tower for $90^\circ$ CW. With these rotations, there are only interactions between the $1^{st}$ and $4^{th}$ towers, and the $2^{nd}$ and $3^{rd}$ towers due to the interesting phenomenon. The $1^{st}$ tower generates $0 + 1000 = 1000$ energy, the $2^{nd}$ tower generates $0 + 1000 = 1000$ energy, the $3^{rd}$ tower generates $1 + 1000 = 1001$ energy, and the $4^{th}$ tower generates $1 + 1000 = 1001$ energy. The total energy generated in this configuration is $4002$.