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 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^◦ angle. Let ( · , · , · , · ) 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^◦, then it radiates (A, B, C, D) as illustrated in the figure on the right.
• If the tower is oriented at 90^◦ (rotated clockwise from 0^◦), then it radiates (D, A, B, C).
• If the tower is oriented at 180^◦ , then it radiates (C, D, A, B).
• If the tower is oriented at 270^◦ , then it radiates (B, C, D, A).

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 ≠ X_j,
2. Y_i ≠ 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 <p, q> are the particles radiated by their facing sides.

• If their facing sides are radiating either <A, C>, <C, A>, <B, D>, or <D, B>, then the i^th tower will generate an interaction energy of G.
• If their facing sides are radiating the same particles, <A, A>,<B, B>, <C, C>, or <D, D>, 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.

Radiates <A, C>	Radiates <D, D>	Radiates <B, C>	X1 = X2
Each tower generates +G energy	Each tower generates -G energy	There is no interaction between these towers	There is no interesting phenomenon that will occur out of these towers

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^◦ 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◦ in any direction will produce 0 energy passively and a tower that is rotated 180^◦ (rotated 90^◦ 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^◦.

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 ≤ N ≤ 50; 1 ≤ R, G, P ≤ 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 ≤ X_i, Y_i ≤ 1000; O_i ∈ {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