UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#1322. Zju2429 Destroying The Graph

Statistics 下载数据

Description

Alice和Bob在玩这样一种游戏:首先,Alice画一个N个顶点M条边的有向图,然后让Bob删去图中所有的边。规则是每步Bob选择一个顶点,然后或者所有指向这个顶点的有向边被删去(操作一),或者所有以这个顶点为起始的有向边被删去(操作二)。 Alice分配两种代价到每一个顶点: Wi+ 和 Wi-. 如果Bob对顶点i执行操作一,那么他将花费$Wi+,反之他将花费$Wi- 请你试着帮Bob找出删去图中所有边的最小花费。

Input

每组输入数据第一行包括N,M(1 <= N <= 100, 1 <= M <= 5000).第二行包括N个整数Wi+.第三行包括N个整数Wi-.所有花费都是正的且不超过10^6.紧跟着M行,每行包括两个整数a, b表示由a向b连接一条有向边.注意,两个顶点间可能有不止一条边,且图中亦存在环.

Output

输出数据第一行包括一个整数W,Bob的最小花费

Sample Input

3 6
1 2 3
4 2 1
1 2
1 1
3 2
1 2
3 1
2 3

Sample Output

5

Hint

Source

Northeastern Europe 2003, Northern Subregion