최소 비용 유량의 역습

플로라는 프리랜서 전서구다. 실력이 뛰어나서 감당할 수 없을 만큼 배달 의뢰가 몰린다. 혼자 다 처리할 수는 없으므로 일부를 전서구 운송 회사에 맡기기로 했다.

도시는 $0$번부터 $N-1$번까지 $N$개 있다. 플로라가 맡기려는 일은 화물 $f$단위를 도시 $s$에서 도시 $t$로 옮기는 것이다. 회사에는 전서구가 $M$마리 있다. $i$번 전서구는 도시 $s_i$에서 도시 $t_i$로 화물을 옮기고, 반대 방향인 $t_i$에서 $s_i$로는 옮기지 못한다. $i$번 전서구가 화물 $u$단위를 옮기는 비용은 $u \le d_i$이면 $u a_i$이고, 그렇지 않으면 $d_i a_i + (u - d_i) b_i$다. 전서구 한 마리가 옮기는 양에는 제한이 없다. 한 전서구가 여러 번에 나누어 옮겨도 비용은 그 전서구가 옮긴 총량으로 계산한다.

플로라는 전체 비용을 최소로 하려고 한다. 최소 비용을 구하라.

첫째 줄에 정수 $N$ ($2 \le N \le 100$), $M$ ($1 \le M \le 1000$), $s$ ($0 \le s \le N-1$), $t$ ($0 \le t \le N-1$), $f$ ($1 \le f \le 200$)가 공백으로 구분되어 주어진다. $s \ne t$다.

다음 $M$개 줄에는 $i$번 전서구의 정보인 정수 $s_i$ ($0 \le s_i \le N-1$), $t_i$ ($0 \le t_i \le N-1$), $a_i$ ($0 \le a_i \le 1000$), $b_i$ ($0 \le b_i \le 1000$), $d_i$ ($1 \le d_i \le 200$)가 주어진다. $a_i < b_i$인 전서구는 많아야 한 마리이고, 나머지 전서구는 모두 $a_i > b_i$를 만족한다.

화물 $f$단위를 도시 $s$에서 도시 $t$로 옮기는 최소 비용을 한 줄에 출력한다. 옮길 수 없으면 Impossible을 출력한다.