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.

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

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

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

18

2 1 0 1 1 1 0 1 0 1

Impossible

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

9

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

14

Source: Japan Alumni Group Spring Contest 2013
, Japan, 2013-04-21

http://jag-icpc.org/

http://jag2013spring.contest.atcoder.jp/

http://jag-icpc.org/

http://jag2013spring.contest.atcoder.jp/