能量网络

【题目描述】

现在有N个点M条有向边组成能源网络图。每一个结点有一个初始值Ai，表示第i个结点可以提供的额外能源供给。

如果结点x到结点y有一条有向边，那么就意味着结点x的需要结点y传输能源。结点x会挑选由它出发的边的终点中，权值最大的点（假设为y）作为能源供给点，花费的代价就是Ay： Wx=max{Ay}  Ay必须满足x到y存在一条有向边。

也就是说补充能源x结点的花费为x结点连接的所有终点y中Ay的最大值。

当然，作为能源提供者的某些点，还可以选择花费额外的Bi的花费将此结点的Ai清为0。

而你现在就要计算一下这个能源网络图所有传输能源的最小花费。

【输入格式】

第一行两个整数N和M

第二行N个整数，A1,A2……AN

第三行N个整数，B1,B2……BN

接下来M行，每行两个整数xj和yj，表示存在xj到yj的一条有向边。

【输出格式】

一个整数，保证这个能源网络图正常运营的最小花费。

【样例输入】

2 1

100000 10000

100000 1

1 2

【样例输出】

1

【提示】

最优方案是花费1的费用将A2改为0。

【数据范围】

 30%     N<=20

 100%    1<=N<=1000  0<=M<=50000  0<=Ai<50000  0<=Bi<=10000

【来源】

在此键入。