Antennas

1D-Land is a single line. Every house is a closed interval $[a, b]$ on that line, and every resident is a point inside their own house. Each resident owns exactly one house.

The carriers MTC1 and MTC2 sell SIM cards, and every resident has already bought a card from one of them. Both carriers now install antennas so that every house of their own subscribers is covered.

An antenna installed at point $x$ has the coverage interval $[x - R, x + R]$. The antenna covers a house when it supports the SIM type of that house's owner and its coverage interval shares at least one point with the house interval. An antenna can be installed at any point of the line, and $R$ is the same for every antenna.

Installing an antenna for MTC1 costs $C_1$ and installing one for MTC2 costs $C_2$. The two carriers also install shared antennas. A shared antenna costs $C_3$ and supports both SIM types. The costs satisfy $\max(C_1, C_2) < C_3 < C_1 + C_2$.

Given the houses, the SIM type of each owner, $R$ and the three costs, find the minimum total cost of a set of antennas that covers every house.

The input holds several test cases. The first line of a test case has five positive integers $n$, $R$, $C_1$, $C_2$, $C_3$. Here $n \le 5000$ is the number of houses, $R \le 10^9$ is the coverage range of an antenna, $C_1$ is the installation cost of an MTC1 antenna, $C_2$ is the installation cost of an MTC2 antenna, and $C_3$ is the installation cost of a shared antenna. All three costs are at most $10^9$. Each of the next $n$ lines describes one house with three integers $a$, $b$, $s$, where $[a, b]$ is the house interval with $0 < a \le b < 10^9$, and $s$ is 1 or 2 and gives the owner's SIM type: 1 for MTC1, 2 for MTC2. The line after the last test case is 0 0 0 0 0 and must not be processed.

For each test case, print one line with the minimum total cost of installing the antennas.