Excursions
Contest: Kotlin Heroes: Episode 7
Tags: *special, constructive algorithms, dfs and similar, flows, graph matchings, graphs

Irina works in an excursion company in Saratov. Today, she is going to organize excursions in the cities of Saratov and Engels.

There are $$$n_1$$$ sights in Saratov and $$$n_2$$$ sights in Engels. The cities are separated by a river, but there are $$$m$$$ bus routes that go along the bridges and allow tourists to go from Saratov to Engels and vice versa. The $$$i$$$-th bus route goes from the $$$x_i$$$-th sight in Saratov to the $$$y_i$$$-th sight in Engels, and in the opposite direction as well.

Irina wants to plan excursions for the current day. The excursion trips start in Saratov in the morning, continue in Engels in the afternoon, and finish in Saratov in the evening.

Each tourist starts their excursion day at some sight in Saratov, $$$k_i$$$ tourists start at the $$$i$$$-th sight. Then the tour guides lead them to Engels: at each sight in Saratov, a tour guide chooses a bus route leading from this sight to Engels, and all the tourists starting from this sight transfer to Engels along this bus route. After the excursions in Engels are finished, the same thing happens: at each sight in Engels, a tour guide chooses a bus route leading from this sight to Saratov, and all the tourists at this sight transfer to Saratov along this bus route.

This process can lead to a situation such that some tourists return to the same sight in Saratov where they started in the morning. Obviously, tourists don't like it; so Irina wants to choose where the tour guides take the tourists (both on the way from Saratov to Engels and on the way from Engels to Saratov), so that the minimum possible number of tourists return to the same sight where they started. Help Irina to find an optimal plan!

Input format:
The first line contains three integers $$$n_1$$$, $$$n_2$$$ and $$$m$$$ ($$$1 \le n_1, n_2 \le 100$$$; $$$\max(n_1, n_2) \le m \le n_1 \cdot n_2$$$) — the number of sights in Saratov, the number of sights in Engels, and the number of bus routes, respectively.

The second line contains $$$n_1$$$ integers $$$k_1, k_2, \dots, k_{n_1}$$$ ($$$1 \le k_i \le 10^6$$$), where $$$k_i$$$ is the number of tourists starting at the $$$i$$$-th sight in Saratov.

Then $$$m$$$ lines follow, each describing a bus route: the $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \le n_1$$$; $$$1 \le y_i \le n_2$$$) meaning that the $$$i$$$-th bus route connects the $$$x_i$$$-th sight in Saratov and the $$$y_i$$$-th sight in Engels. All these bus routes are distinct, and each sight has at least one bus route leading to/from it.

Output format:
Print one integer — the minimum possible number of tourists that will return to the same sight where they started.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
2 1 2
10 20
1 1
2 1

Example output:
10

Example input:
3 3 6
10 20 30
1 3
3 1
2 3
2 1
3 2
1 2

Example output:
0

Editorial:
There is a linear solution to this problem (which I'll describe briefly at the end of this editorial), but our model solution is $$$O(n^4)$$$, that's why the constraints are that low. Guess I'm much less smarter than the top participants, I didn't see any linear solutions before the contest.
Okay, my solution uses minimum cost flows (though it can be formulated with matchings as well). Suppose that all tourists from sight $$$j$$$ in Engels go to sight $$$i$$$ in Saratov. It means that for every sight $$$v$$$ in Saratov such that $$$v \ne i$$$ and there's a bus route from $$$v$$$ to $$$j$$$, we can send all tourists from the sight $$$v$$$ to the sight $$$j$$$, and they won't return to the same sight where they started. Let's say that the sight $$$j$$$ in Engels "fixes" the sight $$$v$$$ in Saratov, if all tourists from sight $$$v$$$ go to sight $$$j$$$ and don't return to the sight $$$v$$$. Obviously, each sight $$$j$$$ in Engels can fix at most $$$d_j - 1$$$ sights in Saratov, where $$$d_j$$$ is the number of bus routes going to the sight $$$j$$$. The answer to the problem is the minimum possible total number of people in the sights of Saratov that are not "fixed".
Let's build a flow network as follows: each sight is represented by a vertex; for every sight $$$j$$$ in Engels, there is an arc from the source to the vertex representing it with a capacity of $$$d_j - 1$$$ and a cost of $$$0$$$, meaning that this sight can "fix" up to $$$d_j - 1$$$ sights in Saratov; for every sight $$$i$$$ in Saratov, there is an arc from the vertex representing it to the sink with a capacity of $$$1$$$ and a cost of $$$-k_i$$$ (meaning that if the $$$i$$$-th sight in Saratov is "fixed", the cost of the flow reduces by $$$k_i$$$); and for every bus route connecting sight $$$x_i$$$ in Saratov and sight $$$y_i$$$ in Engels, there is an arc from the vertex representing $$$y_i$$$ to the vertex representing $$$x_i$$$ with a capacity of $$$1$$$ and a cost of $$$0$$$, meaning that the sight $$$y_i$$$ can "fix" the sight $$$x_i$$$.
Finding the minimum cost flow in this network allows us to "fix" the sights with the maximum possible number of people, so the answer is $$$\sum_{i = 1}^{n} k_i + cost$$$, where $$$cost$$$ is the cost of the flow.
A brief description of linear solution: let's build a bipartite graph representing the sights and bus routes (sights are represented by vertices, bus routes — by edges) and solve the problem for each component of this graph separately. It can be shown that if some component contains a cycle, all tourists in this component can be directed so that nobody returns to the same vertex where they started; otherwise, if a component doesn't contain any cycles, it's sufficient to choose the vertex of the left part with minimum possible $$$k_i$$$ in this component, and the tourists from this vertex will be the only ones which return where they started (all other tourists can be directed so that they move towards this chosen vertex).