시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.5 초 (하단 참고)1024 MB281452913.942%

문제

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

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

예제 입력 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

예제 출력 1

20

세 번째 엘리베이터를 $1$층에서 타고 $11$층에서 내리면 총 $20$초가 소요된다.

예제 입력 2

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

예제 출력 2

19

두 번째 엘리베이터를 $1$층에서 타고 $2$층에서 내린 후, 첫 번째 엘리베이터로 갈아타 $2$층에서 타고 $4$층으로 내리면 총 $3 + 8 \times 2 = 19$초가 소요된다.

예제 입력 3

4 0 4 3
10 1

예제 출력 3

33

계단으로 $1$층에서 $2$층으로 이동하는 데에 $10$초, $2$층에서 $3$층으로 이동하는 데에 $10 + 1 = 11$초, $3$층에서 $4$층으로 이동하는 데에 $10 + 2 \times 1 = 12$초로 총 $10 + 11 + 12 = 33$초가 소요된다.

시간 제한

  • Java 8: 1.5 초
  • Python 3: 1.5 초
  • PyPy3: 1.5 초
  • Java 8 (OpenJDK): 1.5 초
  • Java 11: 1.5 초
  • Kotlin (JVM): 1.5 초
  • node.js: 1.5 초
  • Java 15: 1.5 초