Kotlin Heroes: Episode 7 |
---|

Finished |

The following languages are only available languages for the problems from the contest

Kotlin Heroes: Episode 7:

- Kotlin 1.7.20
- Kotlin 1.9.21

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

*special problem

constructive algorithms

dfs and similar

flows

graph matchings

graphs

No tag edit access

The problem statement has recently been changed. View the changes.

×
I. Excursions

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputIrina 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

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

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

Examples

Input

2 1 2 10 20 1 1 2 1

Output

10

Input

3 3 6 10 20 30 1 3 3 1 2 3 2 1 3 2 1 2

Output

0

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/14/2024 05:10:34 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|