题目描述

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

请你试着帮Bob找出删去图中所有边的最小花费。

输入格式

每组输入数据第一行包括 $N,M(1 \leq N \leq 100, 1 \leq M \leq 5000)$。第二行包括 $N$ 个整数 $W_{i+}$ 。第三行包括 $N$ 个整数$W_{i-}$.所有花费都是正的且不超过 $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

题目来源

Northeastern Europe 2003, Northern Subregion