Description

给出一个有向图D=(V,E).对于每个点U，定义两种操作a(u),b(u)

操作a(u)：删除点U的所有出边，即属于E，操作花费为Ca(u).

操作b(u)：删除点U的所有入边，即属于E，操作花费为Cb(u).

求将原图的边集的边全部删除的最小代价

Format

Input

Input file describes the graph Alice has drawn. The first line of the input file contains N and M (1 <= N <= 100, 1 <= M <= 5000). The second line contains N integer numbers specifying Wi+. The third line defines Wi- in a similar way. All costs are positive and do not exceed 106 . Each of the following M lines contains two integers describing the corresponding arc of the graph. Graph may contain loops and parallel arcs.

Output

On the first line of the output file print W --- the minimal sum Bob must have to remove all arcs from the graph.

Samples

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

5