#P5377. [2018国家队集训队互测]有向图

[2018国家队集训队互测]有向图

[2018国家队集训队互测] 有向图

题目描述

给定一个有 nn 个点、mm 条边的弱连通有向图,即忽略方向后图连通。第 ii 个点初始点权为 did_i。一次修改可以把该点的点权加 11 或减 11,耗时为 wiw_i。

求最小总耗时,使修改后的点权对每条有向边 (u,v)(u,v) 都满足 du≤dvd_u\le d_v。

输入格式

从标准输入读入。第一行两个整数 n,mn,m,表示点数、边数。

第二行 nn 个整数 did_i,表示各点初始点权。第三行 nn 个整数 wiw_i,表示各点一次修改的耗时。

接下来 mm 行,每行两个整数 ui,viu_i,v_i,描述一条从 uiu_i 到 viv_i 的有向边,点编号为 1∼n1\sim n。

对于所有数据,n≤300000n\le300000,m=nm=n 或 m=n−1m=n-1。

输出格式

向标准输出写出一个整数,表示最小总耗时。

样例

输入

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

输出

5

样例解释

限制为 d1≤d2≤d3≤d1d_1\le d_2\le d_3\le d_1,即三者必须相等。把三个点的点权都变为 88,最小耗时为 $1\cdot\lvert5-8\rvert+2\cdot\lvert9-8\rvert+3\cdot\lvert8-8\rvert=5$。