#y0005. 士兵游荡之二

    ID: 9992 传统题 1000ms 256MiB 尝试: 134 已通过: 13 难度: 6 上传者: 标签>CF2000提高Floyd–Warshall二分答案二分图建模最大流Dinic当前弧优化

士兵游荡之二

题目描述

在该国有 nn 个城市和 mm 条带权双向道路连接它们。每个城市都有一支军队。第 ii 个城市的军队由 aia_i 名士兵组成。现在士兵开始同时游荡。游荡后,每名士兵必须要么留在自己的城市,要么走到任意一座城市,走到城市花费的时间为走过的路径长度。

检查在游荡后,第 ii 个城市是否可能最多有 bib_i 名士兵,并求出满足条件所需的最短时间。

输入格式

输入 输入的第一行包含两个整数 nn 和 mm (1 ≤ n ≤ 200,0 ≤ m ≤ 1500)( 1 ≤ n ≤ 200 , 0 ≤ m ≤ 1500 )。 下一行包含 n 个整数 a1, a2, ⋯ , an(0 ≤ ai ≤ 100)a_1, a_2, \cdots, a_n ( 0 ≤ a_i ≤ 100 )。

再下一行包含 nn 个整数 b1, b2, ⋯ , bn(0 ≤ bi ≤ 1000)b_1, b_2, \cdots, b_n ( 0 ≤ b_i ≤ 1000 )。

接下来有 mm 行,每行包含三个整数 p,q,wp,q,w (1 ≤ p, q ≤ n,1≤w≤1000,p ≠ q)( 1 ≤ p, q ≤ n,1\le w\le 1000, p ≠ q ),表示城市 pp 和 qq 之间有一条长度为 ww 的无向道路。

输出格式

如果无法满足条件,则输出 −1-1。 否则输出满足条件所需的最短时间。

样例 #1

样例输入 #1

3 4 
7 0 2
2 4 6
1 2 40 
3 2 70 
2 3 90 
1 3 120

样例输出 #1

110