그래프 파괴하기

앨리스와 밥이 다음 게임을 한다. 먼저 앨리스가 정점 $N$개와 방향 간선(호) $M$개로 이루어진 방향 그래프를 그린다. 그다음 밥은 그래프의 모든 간선을 없애려고 한다. 한 번의 행동에서 밥은 임의의 정점 하나를 골라, 그 정점으로 들어오는 모든 간선을 없애거나, 그 정점에서 나가는 모든 간선을 없앨 수 있다.

앨리스는 각 정점 $i$에 두 개의 비용 $W_i^{+}$와 $W_i^{-}$를 매긴다. 밥이 정점 $i$로 들어오는 모든 간선을 없애면 앨리스에게 $W_i^{+}$달러를 내고, 정점 $i$에서 나가는 모든 간선을 없애면 $W_i^{-}$달러를 낸다. 밥이 그래프의 모든 간선을 없애기 위해 지불해야 하는 최소 금액을 구하라.

첫째 줄에 두 정수 $N$과 $M$이 주어진다 ($1 \le N \le 100$, $1 \le M \le 5000$). 둘째 줄에는 $N$개의 정수 $W_1^{+}, \dots, W_N^{+}$가 주어진다. 셋째 줄에는 같은 방식으로 $W_1^{-}, \dots, W_N^{-}$가 주어진다. 모든 비용은 양의 정수이며 $10^6$을 넘지 않는다. 이어지는 $M$개의 줄에는 각각 두 정수 $a$와 $b$가 주어지며, 정점 $a$에서 정점 $b$로 향하는 간선을 나타낸다. 그래프에는 자기 자신으로 향하는 간선(루프)이나 같은 두 정점을 잇는 평행 간선이 있을 수 있다.

밥이 그래프의 모든 간선을 없애기 위해 지불해야 하는 최소 금액 $W$를 한 줄에 출력한다.