题目描述

给定一个 $n$ 个点 $m$ 条边的有向弱连通图，每个点均有点权 $d_i$ 和修改耗时 $w_i$，每次修改可以花费 $w_i$ 的时间把 $d_i$ 加 $1$ 或者减 $1$，求最少消耗多少时间，使得 $\forall (u,v)\in E, d_u\le d_v$。

输入格式

输入共包括 $m+3$ 行：

第一行包含两个整数 $n,m$，表示点数和边数。

第二行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个点的点权 $d_i$。

第三行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个点的修改耗时 $w_i$。

第 $4$ ~ $m+3$ 行，每行包含两个整数 $u_i,v_i$，表示有向图中的一条由 $u_i$ 到 $v_i$ 的有向边。

输出格式

输出包含一个整数，表示最小总耗时。

样例 1

输入

3 3
5 9 8
1 2 3
1 2
2 3
3 1

输出

5

解释
限制为 $d_1\le d_2$，$d_2\le d_3$，$d_3\le d_1$，即要求 $d_1 = d_2 = d_3$，故将 $d_1$ 加 $3$ 至 $8$，$d_2$ 减 $1$ 至 $8$ 最优，最小耗时为 $1 \times |5-8| + 2\times |9-8| + 3 \times |8-8| = 5$。

样例 2

输入

3 2
5 9 8
1 2 3
1 2
2 3

输出

2

数据范围与提示

子任务表格