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

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

В первой строке даны числа n и k (1 ≤ n ≤ 104, 0 ≤ k ≤ 105) - количество вершин в каждой из долей и количество ребер между долями. Во второй строке перечислены числа ai (1 ≤ ai ≤ 104) - пропускные способности ребер из истока в каждую вершину левой доли. В третьей строке перечислены числа bi (1 ≤ bi ≤ 104) - пропускные способности ребер из каждой вершины правой доли в сток. В каждой из последующих k строк записаны по два числа u и v (1 ≤ u, v ≤ n) означающие наличие ребра и вершины u левой доли в вершину v правой доли.

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

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