eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Максимальный поток B

Максимальный поток B

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Дан двудольный граф, исток и сток. Каждая доля состоит из n вершин. Из истока в левую долю ведут ребра пропускной способности a[i], из каждой вершины правой доли в сток ведут ребра пропускной способности b[i]. Также есть ребра между вершинами левой и правой долей бесконечной пропускной способности, по которым поток может течь как в одну, так и в другую сторону. Найти величину максимального потока из истока в сток.

Входные данные

В первой строке даны числа n и k (1n10^4, 0k10^5) - количество вершин в каждой из долей и количество ребер между долями. Во второй строке перечислены числа a[i] (1a[i]10^4) - пропускные способности ребер из истока в каждую вершину левой доли. В третьей строке перечислены числа b[i] (1b[i]10^4) - пропускные способности ребер из каждой вершины правой доли в сток. В каждой из последующих k строк записаны по два числа u и v (1u, vn) означающие наличие ребра и вершины u левой доли в вершину v правой доли.

Выходные данные

Вывести величину максимального потока.

Пример

Входные данные #1
3 4
3 2 1
5 4 4
1 1
1 2
2 3
3 3
Выходные данные #1
6
Источник III Международная Летняя школа программирования 2012 г. Севастополь