Maximum Flow in a Curved Half‐Plane Straight-Line Same Direction Graph

A directed graph \(G=(V,E)\) is called a curved half‐plane straight-line same direction graph if it can be drawn on a plane such that: all vertices lie on a straight line; any two edges (which may be drawn as curved arcs) only intersect at common endpoints; every point of an edge lies on the same side of the line; and the ray from the start vertex to the end vertex of each edge has the same direction. Given such a graph with \(n\) vertices and \(m\) directed edges, where each edge has a specified capacity, your task is to compute the maximum flow from a given source vertex \(s\) to a sink vertex \(t\).

The graph description guarantees that the special drawing property holds. However, note that the computation of the maximum flow depends solely on the network structure and capacities.

inputFormat

The first line contains four integers \(n\), \(m\), \(s\), and \(t\) where \(1 \leq s,t \leq n\) and \(m\) is the number of edges. Each of the following \(m\) lines contains three integers \(u\), \(v\), and \(w\), representing a directed edge from vertex \(u\) to vertex \(v\) with capacity \(w\). It is guaranteed that \(G\) is a curved half‐plane straight-line same direction graph.

outputFormat

Output a single integer indicating the maximum flow from vertex \(s\) to vertex \(t\).

sample

4 5 1 4
1 2 30
1 3 20
2 3 10
2 4 20
3 4 20

40