시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 15 5 4 36.364%

문제

Flora is a freelance carrier pigeon. Since she is an excellent pigeon, there are too much task requests to her. It is impossible to do all tasks, so she decided to outsource some tasks to Industrial Carrier Pigeon Company.

There are N cities numbered from 0 to N−1. The task she wants to outsource is carrying f freight units from city s to city t. There are M pigeons in the company. The i-th pigeon carries freight from city si to ti, and carrying cost of u units is uai if u is smaller than or equals to di, otherwise diai+(u−di)bi. Note that i-th pigeon cannot carry from city ti to si. Each pigeon can carry any amount of freights. If the pigeon carried freight multiple times, the cost is calculated from total amount of freight units he/she carried.

Flora wants to minimize the total costs. Please calculate minimum cost for her.

입력

The test case starts with a line containing five integers N (2 ≤ N ≤ 100), M (1 ≤ M ≤ 1,000), s (0 ≤ s ≤ N−1), t (0 ≤ t ≤ N−1) and f (1 ≤ f ≤ 200). You may assume s≠t. Each of the next M lines contains five integers si (0 ≤ si ≤ N−1), ti (0 ≤ ti ≤ N−1), ai (0 ≤ ai ≤ 1,000), bi (0 ≤ bi ≤ 1,000) and di (1 ≤ di ≤ 200). Each denotes i-th pigeon's information. You may assume at most one pair of ai and bi satisfies ai < bi, all others satisfies ai > bi.

 

출력

Print the minimum cost to carry f freight units from city s to city t in a line. If it is impossible to carry, print "Impossible" (quotes for clarity).

 

예제 입력

2 2 0 1 5
0 1 3 0 3
0 1 2 1 6

예제 출력

9

예제 입력 2

4 4 0 3 5
0 1 3 0 3
1 3 3 0 3
0 2 2 1 6
2 3 2 1 6

예제 출력 2

18

예제 입력 3

2 1 0 1 1
1 0 1 0 1

예제 출력 3

Impossible

예제 입력 4

2 2 0 1 2
0 1 5 1 2
0 1 6 3 1

예제 출력 4

9

예제 입력 5

3 3 0 2 4
0 2 3 4 2
0 1 4 1 3
1 2 3 1 1

예제 출력 5

14

힌트