说明

你有一个粒子碰撞能量发生器。该发生器是一个二维场，其中有 $N$ 座塔。第 $i$ 座塔位于坐标 $(X_i, Y_i)$ 处，所有塔的作用范围相同，半径为 $R$。每座塔以固定的配置辐射 $4$ 种类型的粒子。具体来说，每座塔在其自身的四个象限（由它的 $x$ 轴和 $y$ 轴分割的区域）中按顺时针方向分别辐射粒子 $A$、$B$、$C$ 和 $D$。塔在其 $x$ 轴或 $y$ 轴上不辐射任何粒子。

初始时，每座塔的朝向为 $90^\circ$ 的整数倍。设 $(\cdot, \cdot, \cdot, \cdot)$ 表示一座塔在其右上、右下、左下、左上象限分别辐射的粒子。

• 如果塔朝向为 $0^\circ$，则它辐射 $(A, B, C, D)$，如右图所示。
• 如果塔朝向为 $90^\circ$（从 $0^\circ$ 顺时针旋转），则它辐射 $(D, A, B, C)$。
• 如果塔朝向为 $180^\circ$，则它辐射 $(C, D, A, B)$。
• 如果塔朝向为 $270^\circ$，则它辐射 $(B, C, D, A)$。

:::align{center} :::

当存在第 $j$ 座塔满足以下条件时，第 $i$ 座塔上可能发生有趣的现象：

1. $X_i \neq X_j$，
2. $Y_i \neq Y_j$，
3. 它们的欧几里得距离不大于 $R$。

有趣的现象如下：设 $p$ 为第 $i$ 座塔在其朝向中第 $j$ 座塔所在象限辐射的粒子，$q$ 为第 $j$ 座塔在其朝向中第 $i$ 座塔所在象限辐射的粒子。为简单起见，称 $\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$ 种组合中的任何一种，则第 $i$ 座塔不与第 $j$ 座塔相互作用。也就是说，这对塔不产生能量。

这种现象是双向的（从每座塔的角度看），并且如果有多座塔满足条件，则会无限叠加。

以下是一些塔对产生能量的示例：

:::align{center} :::

每座塔还被动地产生自身能量。初始时，每座塔自身产生 $P$ 能量。

你可以选择通过旋转来改变每座塔的朝向，从而可能利用有趣的现象增加产生的总能量。沿任意方向（顺时针或逆时针）每旋转 $90^\circ$，会导致该塔被动产生的能量减少 $P$。沿任意方向旋转 $90^\circ$ 的塔被动产生 $0$ 能量，旋转 $180^\circ$（同一方向连续旋转两次 $90^\circ$）的塔被动产生 $-P$ 能量（或者说消耗 $P$ 能量）。注意，你只能将任意塔旋转 $90^\circ$ 的整数倍。

你的任务是找出通过任意改变零座或多座塔的朝向所能产生的最大总能量。一种配置下产生的总能量等于该配置中每座塔因被动或因与其他塔相互作用而产生的能量之和。

输入格式

输入第一行包含 $4$ 个整数 $N$、$R$、$G$ 和 $P$（$1 \leq N \leq 50$；$1 \leq R, G, P \leq 1000$），分别表示塔的数量、所有塔的作用半径、塔相互作用能量常数以及每座塔初始被动产生的能量。接下来 $N$ 行，每行包含 $3$ 个整数 $X_i$、$Y_i$ 和 $O_i$（$-1000 \leq X_i, Y_i \leq 1000$；$O_i \in \{0, 90, 180, 270\}$），表示第 $i$ 座塔的位置和初始朝向。保证没有两座塔位置相同。

输出格式

输出一行一个整数，表示在所有可能的塔的配置中能产生的最大总能量。

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

提示

样例 #1 解释

最大总能量可通过将第 $2$ 座塔旋转 $180^\circ$ 获得。第 $3$ 座塔与任何其他塔的欧几里得距离均大于 $R$，因此不会发生有趣现象。不旋转第 $3$ 座塔，它被动产生 $15$ 能量。将第 $2$ 座塔旋转 $180^\circ$ 后其朝向变为 $0^\circ$。第 $1$ 座塔和第 $2$ 座塔之间发生有趣现象，因为它们满足所有条件，且相对面辐射的粒子为 $\langle A, C \rangle$（从第 $2$ 座塔角度看则为 $\langle C, A \rangle$）。第 $1$ 座塔通过被动能量和与第 $2$ 座塔的相互作用产生 $15 + 10 = 25$ 能量，而第 $2$ 座塔产生 $-15 + 10 = -5$ 能量。此配置下三座塔总能量为 $25 - 5 + 15 = 35$。

样例 #2 解释

最大总能量可通过不进行任何旋转获得。这三座塔在当前朝向下相互影响。第 $1$ 座和第 $2$ 座塔各产生 $1 + (-1) = 0$ 相互作用能量，第 $3$ 座塔产生 $-1 + (-1) = -2$ 相互作用能量。每座塔还被动产生 $1000$ 能量。此配置下总能量为 $2998$。

样例 #3 解释

最大总能量可通过将第 $1$ 座塔逆时针旋转 $90^\circ$、第 $2$ 座塔顺时针旋转 $90^\circ$ 获得。旋转后，只有第 $1$ 座与第 $4$ 座、第 $2$ 座与第 $3$ 座之间因有趣现象产生相互作用。第 $1$ 座塔产生 $0 + 1000 = 1000$ 能量，第 $2$ 座塔产生 $0 + 1000 = 1000$ 能量，第 $3$ 座塔产生 $1 + 1000 = 1001$ 能量，第 $4$ 座塔产生 $1 + 1000 = 1001$ 能量。此配置下总能量为 $4002$。

翻译由 DeepSeek 完成