Description

小w开了一家快递公司，在n个城市之间进行货物运输工作，一共雇了m个快递员。每个快递员性格很奇特，第i号快递员只愿意将货物从城市si运送到ti（甚至不愿意将货物从ti运送到si），并且如果他运送的货物量x<=di，那么他要求获得的报酬为xai，否则为diai+(x-di)*bi。

现在小w接到一个大订单，需要将f单位货物从s运送到t，请求出小w的最小开支。

你可以假定每个快递员的运货量没有限制。

Input Format

第一行五个整数n，m，s，t，f

接下来m行每行五个数si,ti,ai,bi,di，描述一个快递员的信息。

Output Format

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

Sample

输入： 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

Hint

n<=100,m<=1000,si,ti,s,t<=n-1,f,di<=200,ai,bi<=1000

保证至多只有一名邮递员ai<bi,其余均是ai>bi

共50组数据，保证数据有梯度。