BZPRO
#1322. Zju2429 Destroying The Graph
内存限制：64 MiB
时间限制：1 Sec
提交
提交记录
讨论
题目描述
Alice和Bob在玩这样一种游戏：首先，Alice画一个N个顶点M条边的有向图,然后让Bob删去图中所有的边。规则是每步Bob选择一个顶点，然后或者所有指向这个顶点的有向边被删去(操作一)，或者所有以这个顶点为起始的有向边被删去(操作二)。 Alice分配两种代价到每一个顶点: Wi+ 和 Wi-. 如果Bob对顶点i执行操作一,那么他将花费$Wi+，反之他将花费$Wi- 请你试着帮Bob找出删去图中所有边的最小花费。
输入格式
每组输入数据第一行包括N，M(1 <= N <= 100, 1 <= M <= 5000).第二行包括N个整数Wi+.第三行包括N个整数Wi-.所有花费都是正的且不超过10^6.紧跟着M行，每行包括两个整数a, b表示由a向b连接一条有向边.注意，两个顶点间可能有不止一条边，且图中亦存在环.
输出格式
输出数据第一行包括一个整数W,Bob的最小花费
样例
样例输入
3 6
1 2 3
4 2 1
1 2
1 1
3 2
1 2
3 1
2 3
样例输出
5
数据范围与提示
BZPRO