우혁이와 엘리베이터

시간 제한0.5초메모리 제한1024 MB

요약

정해진 층에만 서는 엘리베이터와, 쓸수록 비용이 커지는 계단을 최대 K층까지 섞어 1층에서 E층까지 가는 최소 시간을 구한다.

문제

국민대학교 북악관은 $1$ 층부터 $N$ 층까지 있고, $M$ 개의 엘리베이터가 있다. 각 엘리베이터는 $1$ 부터 $N$ 까지의 정수 중 임의의 수가 적힌 버튼들을 가지고 있고, 버튼에 적힌 수들에 해당하는 층만을 운행한다.

우혁이가 층과 층 사이를 이동하는 방법이 두 가지 있는데, 다음과 같다.

엘리베이터의 버튼이 있는 층에서 다른 버튼이 있는 층으로 이동한다. $i$ 번째 엘리베이터는 한 층을 이동하는 데 $t\_i$ 의 시간이 걸린다. 예를 들어 $3$ 층에서 $5$ 층을 가는 데에 $2 \times t\_i$ 만큼의 시간이 걸린다.
계단을 통하여 한 층 위 또는 한 층 아래로 이동한다. $1$ 층에서는 한 층 아래로 이동할 수 없고, $N$ 층에서는 한 층 위로 이동할 수 없다. 체력이 좋지 못한 우혁이는 모든 이동을 통틀어 최대 $K$ 층만큼만 계단으로 다닐 수 있으며, 체력 소모로 인하여 계단을 이용할 때마다 계단을 통한 이동 시간이 단조증가한다. 구체적으로 이전까지 $n$ 개의 층을 계단으로 이동한 경우, 계단을 통해 이동할 때 $T\_1+n \times T\_2$ 만큼의 시간이 걸린다. $(0 \leq n < K)$

엘리베이터와 계단 사이의 이동 시간은 무시한다고 할 때, 건물 $1$ 층에 막 도착한 우혁이가 $E$ 층에 도착할 수 있는 최소 시간을 구해보자.

첫째 줄에 네 정수 $N, M, E, K$ 가 공백으로 구분되어 주어진다.

둘째 줄에 두 정수 $T\_1$ 과 $T\_2$ 가 공백으로 구분되어 주어진다.

셋째 줄부터 $M$ 개의 줄에 걸쳐, $i$ 번째 엘리베이터의 정보 $c\_i, t\_i, x\_1, x\_2, \ldots, x\_{c\_i}$ 가 공백으로 구분되어 주어진다. $(1 \leq i \leq M)$

우혁이가 $1$ 층에서 출발하여 $E$ 층에 도착할 수 있다면 우혁이가 $E$ 층에 도착하는 최소 시간을 출력한다.

만약 우혁이가 $E$ 층에 도착할 수 없다면 -1을 출력한다.

입력으로 주어지는 수는 모두 정수이다.

예제 1

입력

16 5 11 5
10 5
3 3 1 5 9
4 5 1 7 13 15
2 2 1 11
3 3 1 6 10
5 5 1 5 8 12 14

예상 출력

예제 2

입력

8 2 4 0
10 0
8 8 8 7 6 5 4 3 2 1
4 3 8 5 2 1

예상 출력