Maximize Scientific Expedition Profit

On May Fourth Youth Day, the young explorer NiuNiu leads his scientific expedition team to explore a pristine forest. The forest has \(n\) gathering points numbered from \(1\) to \(n\), and \(m\) directed paths connecting these points. Each path is defined by its starting point \(u\) and ending point \(v\). When a team traverses a path, they collect valuable data with a value of \(r\), but if the path requires to be forged (or opened), a cost \(c\) is incurred. Even if multiple teams use the same path, the data value and the forging cost are both counted only once.

The expedition consists of \(p\) teams. All teams start from node \(S\) and eventually regroup at node \(T\). Although teams might choose different routes due to differing equipment—some paths being too difficult for certain teams—NiuNiu ensures that each team can reach \(T\) by wisely distributing the available equipment. In effect, it is always possible for every team to reach \(T\), and they are free to share the same path if that maximizes the overall benefit.

The total net profit of the expedition is the sum of the data values collected (without duplication) minus the sum of the forging costs incurred (again, each cost is paid only once even if several teams use that path). NiuNiu’s goal is to plan the routes for the \(p\) teams so that this net profit is maximized.

You are given the map of the forest. Even though \(p\) teams are involved, note that since the cost and reward of each edge are counted only once regardless of the number of teams traversing it, the optimal strategy is to select a set of paths that connects \(S\) to \(T\) (possibly, a single route) with maximum net gain.

Formally, given a directed graph with \(n\) nodes and \(m\) edges, where each edge from \(u\) to \(v\) has a gain of \(r\) and a cost of \(c\), find a set of edges (i.e. a subgraph) containing at least one \(S\)-\(T\) path such that the value \[ \text{profit} = \sum_{e \in E'} r_e - \sum_{e \in E'} c_e \] is maximized. If there is no path from \(S\) to \(T\), output "impossible".

inputFormat

The first line contains five integers \(n\), \(m\), \(p\), \(S\), and \(T\):

• \(n\): the number of gathering points (nodes).
• \(m\): the number of directed paths (edges).
• \(p\): the number of teams (note that due to cost sharing, this parameter does not affect the optimal selection of paths).
• \(S\): the starting node.
• \(T\): the target node.

Each of the following \(m\) lines contains four integers \(u\), \(v\), \(r\), and \(c\), describing a directed edge from node \(u\) to node \(v\) that provides a data value of \(r\) and requires a forging cost of \(c\).

outputFormat

If there exists an \(S\)-\(T\) path, output a single integer representing the maximum net profit obtainable (i.e. total data value minus forging cost, with each edge counted only once). Otherwise, output "impossible".

sample

4 5 3 1 4
1 2 5 3
2 4 7 2
1 3 4 1
3 4 6 3
2 3 2 2

7