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

### 问题描述

Flora是一只自由职业的信鸽。由于她是一只出色的信鸽，有太多的任务请求她。不可能完成所有任务，所以她决定将一些任务外包给工业运输公司。

有N个编号从0到N-1的城市。她想要外包的任务是从城市s到城市t运输f个货物单位。公司里有M只信鸽。第i只信鸽从城市s_i到城市t_i携带货物，并且当u小于或等于d_i时，运送u个单位的成本为u*a_i，否则为d_i*a_i+(u-d_i)*b_i。注意，第i只信鸽不能从城市t_i到城市s_i。每只信鸽可以携带任意数量的货物。如果信鸽多次携带货物，成本是根据他/她携带的货物总量计算的。

Flora想要最小化总成本。请计算最小成本。

* * *

### 输入

测试用例以一行包含五个整数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$)和f ($1 \\leq f \\leq 200$)开始。可以假设$s \\neq t$。接下来的M行中，每行包含五个整数$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$)和$d_i$ ($1 \\leq d_i \\leq 200$)。每个数字表示第i只信鸽的信息。可以假设最多有一对$a_i$和$b_i$满足$a_i < b_i$，其他都满足$a_i > b_i$。

### 输出

在一行中打印从城市s到城市t运输f个货物单位的最小成本。如果无法运输，请打印"Impossible"（带引号）。

### 样例输入1

```plain

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

样例输出1

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

来源名称

日本校友团体春季竞赛2013