【题目描述】
小w开了一家快递公司，在n个城市之间进行货物运输工作，一共雇了m个快递员。每个快递员性格很奇特，第i号快递员只愿意将货物从城市si运送到ti（甚至不愿意将货物从ti运送到si），并且如果他运送的货物量x<=di，那么他要求获得的报酬为x* ai，否则为di * ai+(x-di) * bi。
现在小w接到一个大订单，需要将f单位货物从s运送到t，请求出小w的最小开支。
你可以假定每个快递员的运货量没有限制。

【输入格式】
第一行五个整数n，m，s，t，f
接下来m行每行五个数si,ti,ai,bi,di，描述一个快递员的信息。

【输出格式】
如有解请输出最小小开支，否则请输出“Impossible”。（不含引号）

Sample 1

Input

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

18

Limitation

1s, 1024KiB for each test case.
【数据范围】
n<=100,m<=1000,si,ti,s,t<=n-1,f,di<=200,ai,bi<=1000
保证至多只有一名邮递员ai<bi,其余均是ai>bi
共50组数据，保证数据有梯度。