Max has been sending a LOT of letters recently. So much so that he's run out of paper! Max, being again, a marvellous algorithmic influencer orders stationary from the online shopping giant Redwood.

The boffins at Redwood are looking to improve their shipping margins and Max's orders are so voluminous they consider the case of shipping some quantity of paper \(P\) from their shipping outlet to Max through a variety of postal routes, each with their own capacity and cost per unit paper.

Given a representation of the postal system as a list of intermediate routes from Redwood to Max, each with a capacity and cost compute the minimum cost of sending \(P\) units of paper to Max. Additionally, if it is not possible to ship the required order at once, Max will need to be notified accordingly.

Input Specification

The first line contains three integers \(V, E, P\), \(1 \leq V \leq 100\), \(1 \leq E \leq V\), \(1 \leq P \leq 1000\), the number of intermediate postage locations (including Redwood and Max), the number of intermediate routes and the volume of paper Max has ordered respectively.

The next \(E\) lines contain four integers, \(u, v, c_a, c_s\), \(0 \leq u, v < V | u \neq v\), \(1 \leq c_a, c_s \leq 1000\), the sending location, receiving location, capacity and cost of a single intermediate route respectively.

The final line contains two integers \(r, m\), \(1 \leq, r, m < V | r \neq m\), the locations of Redwood and Max respectively.

Furthermore, you are guaranteed all postage routes work in a single direction.

Output Specification

If it is possible to send the requested amount of paper to Max print a single integer, the minimum cost of doing so.

If it is not possible to send the requested amount of paper to Max print -1.

Sample Input 1

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

Sample Output 1

7

Sample Input 2

3 2 10
0 1 5 1
1 2 8 2
0 2

Sample Output 2

-1