你拥有一个粒子碰撞能量发生器。该发生器是一个包含 $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)$。

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

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

有趣的现象如下：设 $p$ 为第 $i$ 个塔在第 $j$ 个塔所在象限辐射的粒子，$q$ 为第 $j$ 个塔在第 $i$ 个塔所在象限辐射的粒子。为简便起见，我们称 $p, q$ 为它们面对面一侧辐射的粒子。

• 如果它们面对面的一侧辐射的粒子为 $\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$ 个塔之间不产生相互作用。换句话说，这对塔之间不产生能量。

此现象双向适用（从每个塔的角度来看），并且如果存在多个满足条件的塔，则能量可以无限叠加。

每个塔还会被动地产生自身的能量。最初，每个塔自身产生 $P$ 的能量。

你可以选择通过旋转来改变每个塔的朝向，从而可能利用这种有趣的现象并增加产生的总能量。每个 $90^\circ$ 的旋转（无论是顺时针还是逆时针）都会导致塔被动产生的能量减少 $P$。旋转 $90^\circ$ 的塔被动产生 $0$ 能量，旋转 $180^\circ$（在同一方向旋转两次 $90^\circ$）的塔被动产生 $-P$ 能量（换句话说，消耗 $P$ 能量）。注意，你只能将任何塔旋转 $90^\circ$ 的倍数。

你的任务是找到通过以任何方式改变零个或多个塔的朝向所能产生的最大总能量。配置中产生的总能量是每个塔被动产生的能量与配置中与其他塔相互作用产生的能量之和。

输入格式

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

输出格式

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

样例

样例输入 1

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

样例输出 1

35

样例输入 2

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

样例输出 2

2998

样例输入 3

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

样例输出 3

4002

Figure 1. 塔的辐射配置示意图