#P5377. [2018国家队集训队互测]有向图
[2018国家队集训队互测]有向图
[2018国家队集训队互测] 有向图
题目描述
给定一个有 个点、 条边的弱连通有向图,即忽略方向后图连通。第 个点初始点权为 。一次修改可以把该点的点权加 或减 ,耗时为 。
求最小总耗时,使修改后的点权对每条有向边 都满足 。
输入格式
从标准输入读入。第一行两个整数 ,表示点数、边数。
第二行 个整数 ,表示各点初始点权。第三行 个整数 ,表示各点一次修改的耗时。
接下来 行,每行两个整数 ,描述一条从 到 的有向边,点编号为 。
对于所有数据,, 或 。
输出格式
向标准输出写出一个整数,表示最小总耗时。
样例
输入
3 3
5 9 8
1 2 3
1 2
2 3
3 1
输出
5
样例解释
限制为 ,即三者必须相等。把三个点的点权都变为 ,最小耗时为 $1\cdot\lvert5-8\rvert+2\cdot\lvert9-8\rvert+3\cdot\lvert8-8\rvert=5$。