34038번 - 우혁이와 엘리베이터

문제

국민대학교 북악관은 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)$

• $c_i$: 엘리베이터가 운행하는 층의 개수
• $t_i$: 층 하나를 이동하는 데 걸리는 시간
• $x_1 , x_2 , \ldots , x_{c_i}$: 엘리베이터가 운행하는 층 번호들로, 중복 없이 주어진다.

출력

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

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

제한

• 1ドル\leq N \leq 500$
• 0ドル \leq M \leq 500$
• 1ドル \leq E \leq N$
• 0ドル \leq K \leq 50$
• 0ドル \leq T_1, T_2, t_i \leq 100,000円$
• 2ドル \leq c_i \leq N$
• 1ドル \leq x_i \leq N$

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

힌트