题目描述

Alice 和 Bob 玩下面这个游戏。

首先，Alice 画出一张有 $N$ 个顶点、$M$ 条弧的有向图。随后 Bob 要设法摧毁这张图。

一次操作中，Bob 可以选择图中的任意一个顶点，并执行以下两种操作之一：

1. 删除所有进入这个顶点的弧；
2. 删除所有从这个顶点出发的弧。

Alice 给每个顶点 $i$ 设置了两个费用：

• $W_i^+$：删除所有进入第 $i$ 个顶点的弧所需支付的费用；
• $W_i^-$：删除所有从第 $i$ 个顶点出发的弧所需支付的费用。

请你求出 Bob 删除图中所有弧所需支付的最小总费用，并输出一种达到最小费用的操作方案。

图中可能存在自环，也可能存在重边。

输入格式

第一行包含两个整数 $N,M$，表示图的顶点数和弧数。

第二行包含 $N$ 个整数，依次表示：

第三行包含 $N$ 个整数，依次表示：

接下来 $M$ 行，每行包含两个整数 $u,v$，表示图中有一条从 $u$ 指向 $v$ 的弧。

输出格式

第一行输出一个整数 $W$，表示 Bob 删除所有弧所需支付的最小总费用。

数据范围

对于所有测试数据，满足：

所有费用均为正整数，且不超过 $10^6$。

图中可能存在自环和重边。

样例

输入

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

输出

5

样例解释

一种最优方案如下：

1. 对顶点 $1$ 执行 + 操作，删除所有进入顶点 $1$ 的弧；
2. 对顶点 $2$ 执行 - 操作，删除所有从顶点 $2$ 出发的弧；
3. 对顶点 $2$ 执行 + 操作，删除所有进入顶点 $2$ 的弧。

总费用为：

可以证明不存在费用更小的方案。