10639번 - Revenge of Minimum Cost Flow

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 ua_i if u is smaller than or equals to d_i, otherwise d_ia_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 ≤ N ≤ 100), M (1 ≤ M ≤ 1,000), s (0 ≤ s ≤ N−1), t (0 ≤ t ≤ N−1) and f (1 ≤ f ≤ 200). You may assume s≠t. Each of the next M lines contains five integers s_i (0 ≤ s_i ≤ N−1), t_i (0 ≤ t_i ≤ N−1), a_i (0 ≤ a_i ≤ 1,000), b_i (0 ≤ b_i ≤ 1,000) and d_i (1 ≤ d_i ≤ 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).