철도 연결

도쿄의 철도망은 매우 복잡하다. 아래 그림은 노선과 역의 일부를 나타낸 지도이다.

철도망 예시.

A역에서 D역으로 가려고 한다고 하자. 거리가 가장 짧은 경로는 분명히 A → B → D이다. 그러나 가장 짧은 경로가 항상 가장 저렴한 것은 아니다. 예를 들어 A–B, B–C, C–D 노선은 한 철도 회사가 운영하고 B–D 노선은 다른 회사가 운영한다고 하자. 이때 A → B → C → D 경로의 요금이 A → B → D 경로보다 더 적게 들 수 있다.

그 이유는 요금이 거리에 정비례하지 않기 때문이다. 보통 이동 거리가 길수록 단위 거리당 요금은 낮아진다. 서로 다른 회사의 노선을 이용하면 각 회사가 부과한 요금이 단순히 합산되므로, 짧지만 여러 회사를 섞어 쓰는 경로가 오히려 더 비쌀 수 있다.

여러 회사가 포함된 철도망과 각 회사의 요금표(거리로부터 요금을 계산하는 규칙), 그리고 출발역과 도착역이 주어질 때, 가능한 최소 총요금을 계산하는 프로그램을 작성하여라.

입력은 여러 개의 데이터셋으로 이루어지며, 각 데이터셋의 형식은 다음과 같다.

n m c s g
x_1 y_1 d_1 c_1
...
x_m y_m d_m c_m
p_1 ... p_c
q_1,1 ... q_1,(p_1 - 1)
r_1,1 ... r_1,p_1
...
q_c,1 ... q_c,(p_c - 1)
r_c,1 ... r_c,p_c

모든 값은 음이 아닌 정수이며, 같은 줄의 값은 공백 하나로 구분된다.

첫 번째 줄은 철도망과 이동 정보를 나타낸다. $n$은 역의 수 ($2 \le n \le 100$), $m$은 두 역을 잇는 노선의 수 ($0 \le m \le 10000$), $c$는 철도 회사의 수 ($1 \le c \le 20$)이다. $s$는 출발역 번호, $g$는 도착역 번호이다 ($1 \le s, g \le n$, $g \ne s$).

이어지는 $m$개의 줄은 각 노선을 설명한다. $i$번째 노선은 역 $x_i$와 $y_i$를 잇고 ($1 \le x_i, y_i \le n$, $x_i \ne y_i$) 양방향으로 이동할 수 있다. 같은 두 역을 잇는 노선이 여러 개 있을 수 있다. $d_i$는 노선의 길이 ($1 \le d_i \le 200$), $c_i$는 그 노선을 운영하는 회사의 번호이다 ($1 \le c_i \le c$).

각 회사의 요금표는 거리에 대한 구간별 선형 함수이다. 회사 $j$에 대해 $p_j$는 구간의 개수 ($1 \le p_j \le 50$)이다. $q_{j,k}$ ($1 \le k \le p_j - 1$, $1 \le q_{j,k} \le 10000$)는 구간이 바뀌는 거리이고, $r_{j,k}$ ($1 \le k \le p_j$, $1 \le r_{j,k} \le 100$)는 구간 $k$에서 단위 거리마다 추가되는 요금이다. 거리 $z$에 대한 요금을 $f_j(z)$라 하면,

$f_j(z) = f_j(z-1) + r_{j,k} \quad (q_{j,k-1}+1 \le z \le q_{j,k})$

이 성립하며, $q_{j,0} = 0$, $f_j(0) = 0$, $q_{j,p_j} = \infty$ 이다.

예를 들어 $p_j = 3$, $q_{j,1} = 3$, $q_{j,2} = 6$, $r_{j,1} = 10$, $r_{j,2} = 5$, $r_{j,3} = 3$이면 요금표는 다음과 같다.

$q_{j,k}$는 $k$에 대해 증가하고, $r_{j,k}$는 $k$에 대해 감소한다.

마지막 데이터셋 다음에는 공백으로 구분된 다섯 개의 0으로 이루어진 줄이 오며, 이 줄은 처리하지 않는다.

각 데이터셋에 대해, 출발역에서 도착역까지 가는 경로의 최소 총요금을 한 줄에 출력한다. 도착역에 도달할 수 없으면 대신 -1을 출력한다. 뒤따르는 공백 등 불필요한 문자는 출력하지 않는다.

경로가 정해지면 총요금은 다음과 같이 계산한다. 경로를 같은 회사가 연속으로 운영하는 노선들의 최대 묶음으로 나눈다. 각 묶음에 대해 그 안의 노선 길이를 모두 더한 뒤, 그 합산 거리로 해당 회사의 요금표에서 요금을 구한다. 경로의 총요금은 이러한 묶음별 요금의 합이다. 같은 회사의 두 노선 사이에 다른 회사의 노선이 끼어 있으면, 그 두 노선은 서로 다른 묶음에 속하며 요금은 독립적으로 계산된다. 어떤 회사도 환승 할인을 제공하지 않는다.