최소 비용 유량의 역습

시간 제한3초메모리 제한256 MB

요약

두 구간 선형 비용을 가진 방향 간선을 이용해 도시 s에서 도시 t까지 화물 f단위를 최소 총비용으로 운송합니다.

난이도: 어려움10점 중 9점
유형: 그래프, 최단 경로, 동적 계획법
정답자: 아직 제출이 없습니다

문제

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

도시는 $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을 출력한다.

예제5

예제 1
입력
```
2 2 0 1 5
0 1 3 0 3
0 1 2 1 6
```
예상 출력
```
9
```

예제 2

입력

예상 출력

예제 3
입력
```
2 1 0 1 1
1 0 1 0 1
```
예상 출력
```
Impossible
```
예제 4
입력
```
2 2 0 1 2
0 1 5 1 2
0 1 6 3 1
```
예상 출력
```
9
```

예제 5

입력

예상 출력