안테나

1차원 세계는 직선 하나다. 이 세계에서 집은 직선 위의 닫힌 구간 $[a, b]$이고, 주민은 자기 집 안의 한 점이다. 주민마다 집이 정확히 하나씩 있다.

이동통신사 MTC1과 MTC2는 SIM 카드를 판다. 주민은 모두 두 회사 중 한 곳에서 SIM 카드를 이미 샀다. 이제 두 회사는 자기 가입자의 집이 모두 서비스 범위에 들어오도록 안테나를 설치한다.

점 $x$에 설치한 안테나의 서비스 구간은 $[x - R, x + R]$이다. 안테나가 집주인의 SIM 종류를 지원하고 안테나의 서비스 구간과 집 구간이 적어도 한 점을 공유하면, 그 안테나가 그 집을 담당한다고 한다. 안테나는 직선 위 어느 점에나 설치할 수 있고, 모든 안테나의 $R$은 같다.

MTC1 전용 안테나의 설치 비용은 $C_1$, MTC2 전용 안테나의 설치 비용은 $C_2$다. 두 회사는 공용 안테나도 설치한다. 공용 안테나의 설치 비용은 $C_3$이고, 두 종류의 SIM을 모두 지원한다. 비용은 $\max(C_1, C_2) < C_3 < C_1 + C_2$를 만족한다.

집의 정보와 집주인의 SIM 종류, $R$, 세 비용이 주어질 때, 모든 집을 담당하는 안테나 집합의 최소 총비용을 구하라.

입력에는 테스트 케이스가 여러 개 들어 있다. 각 테스트 케이스의 첫 줄에는 양의 정수 다섯 개 $n$, $R$, $C_1$, $C_2$, $C_3$가 주어진다. $n \le 5000$은 집의 개수, $R \le 10^9$은 안테나의 서비스 반경, $C_1$은 MTC1 안테나의 설치 비용, $C_2$는 MTC2 안테나의 설치 비용, $C_3$은 공용 안테나의 설치 비용이다. 세 비용은 모두 $10^9$ 이하다. 이어지는 $n$개의 줄에는 집 하나의 정보가 정수 세 개 $a$, $b$, $s$로 주어진다. $[a, b]$는 집 구간이고 $0 < a \le b < 10^9$이며, $s$는 1 또는 2로 집주인의 SIM 종류를 나타낸다. 1은 MTC1, 2는 MTC2다. 마지막 테스트 케이스 다음 줄에는 0 0 0 0 0이 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 안테나 설치 비용의 최솟값을 한 줄에 출력한다.