$(function(){document.getElementById("fixed-server-timer").style.display = "none";})

Problem Statement

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 $s_i$ to $t_i$, and carrying cost of $u$ units is $u a_i$ if $u$ is smaller than or equals to $d_i$, otherwise $d_i a_i + (u-d_i)b_i$. Note that $i$-th pigeon cannot carry from city $t_i$ to $s_i$. 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.

Input

The test case starts with a line containing five integers $N$ ($2 \\leq N \\leq 100$), $M$ ($1 \\leq M \\leq 1{,}000$), $s$ ($0 \\leq s \\leq N-1$), $t$ ($0 \\leq t \\leq N-1$) and $f$ ($1 \\leq f \\leq 200$). You may assume $s \\neq t$. Each of the next $M$ lines contains five integers $s_i$ ($0 \\leq s_i \\leq N-1$), $t_i$ ($0 \\leq t_i \\leq N-1$), $a_i$ ($0 \\leq a_i \\leq 1{,}000$), $b_i$ ($0 \\leq b_i \\leq 1{,}000$) and $d_i$ ($1 \\leq d_i \\leq 200$). Each denotes $i$-th pigeon's information. You may assume at most one pair of $a_i$ and $b_i$ satisfies $a_i < b_i$, all others satisfies $a_i > b_i$.

Output

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).

Sample Input 1

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

Output for the Sample Input 1

9

Sample Input 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

Output for the Sample Input 2

18

Sample Input 3

2 1 0 1 1
1 0 1 0 1

Output for the Sample Input 3

Impossible

Sample Input 4

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

Output for the Sample Input 4

9

Sample Input 5

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

Output for the Sample Input 5

14

Source Name

Japan Alumni Group Spring Contest 2013