P0643

Zju2429 Destroying The Graph

Zju2429 Destroying The Graph

Alice 和 Bob 正在玩一个游戏。首先，Alice 画出一张包含 NN 个顶点和 MM 条边的有向图，然后要求 Bob 删除图中的所有边。

每一步，Bob 选择一个顶点，并执行以下两种操作之一：

  • 操作一：删除所有指向该顶点的有向边；
  • 操作二：删除所有从该顶点出发的有向边。

Alice 为每个顶点 ii 分配了两种操作代价 Wi+W_i^+ 和 Wi−W_i^-。若 Bob 对顶点 ii 执行操作一，则需要花费 Wi+W_i^+；若执行操作二，则需要花费 Wi−W_i^-。

请帮助 Bob 求出删除图中所有边所需的最小总花费。

输入格式

第一行包含两个整数 NN 和 MM，分别表示有向图的顶点数和边数。

第二行包含 NN 个整数，其中第 ii 个整数为 Wi+W_i^+。

第三行包含 NN 个整数，其中第 ii 个整数为 Wi−W_i^-。

接下来 MM 行，每行包含两个整数 aa 和 bb，表示存在一条从顶点 aa 指向顶点 bb 的有向边。

两个顶点之间可能存在多条同向边，图中也可能存在自环。

输出格式

输出一个整数 WW，表示 Bob 删除图中所有边所需的最小总花费。

样例输入

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

样例输出

5

数据范围

  • 1≤N≤1001\le N\le 100；
  • 1≤M≤50001\le M\le 5000；
  • 1≤Wi+≤1061\le W_i^+\le 10^6；
  • 1≤Wi−≤1061\le W_i^-\le 10^6。

来源与许可

本题为 ZJU 2429「Destroying The Graph」，题面与测试数据整理自 BZOJ 1322。

样例 1

输入

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

输出

5