408541: GYM103182 J Strategy

The Kingdom of AGM is the next target of the emperor. The kingdom is shaped as a directed acyclic graph. Commander Nix would have to guide his soldiers through the country starting from city $$$X$$$ (the border), all the way to city $$$Y$$$ (the capital). Alongside some of the roads in the kingdom, there are important settlements that also need to be conquered. Thus, before reaching the capital, the commander would have to make sure that for the road going from city $$$a_i$$$ to $$$b_i$$$ at least $$$c_i$$$ soldiers will traverse it. Having studied the resources available in the area, he also concluded that it would be impossible to have more than $$$d_i$$$ soldiers travel the road going from city $$$a_i$$$ to $$$b_i$$$.

In order to figure out if the mission should be approved, the emperor asked you to find out how many soldiers can reach the capital, considering Commander Nix's insight.

Keep in mind that no soldier should be abandoned. Thus, if not all soldiers that would take the mission can reach the capital, the mission is considered a failure.

The first line of the input contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 500$$$ and $$$1 \leq M \leq 1100$$$), the number of cities, the number of rules and the number of soldiers that must reach the capital.

The second line will contain two integers $$$X$$$ and $$$Y$$$ ($$$1 \leq X, Y \leq N$$$, $$$X \ne Y$$$), the border and the capital, respectively.

The next $$$M$$$ lines will each contain four integers $$$a_i$$$ ($$$1 \leq a_i \leq N$$$), $$$b_i$$$ ($$$1 \leq b_i \leq N$$$, $$$a_i \ne b_i$$$), $$$c_i$$$, $$$d_i$$$ ($$$0 \leq c_i \leq d_i \leq 10^9$$$), signifying that along the road from city $$$a_i$$$ to city $$$b_i$$$ should travel at least $$$c_i$$$ and at most $$$d_i$$$ soldiers.

If the mission can be accomplished output the maximum number of soldiers that can reach the capital, otherwise output 0.

4 5
1 3
1 2 0 7
1 4 0 4
2 3 0 2
4 2 1 1
4 3 1 5

5