现在是30世纪,狐狸Shieru是雨神,控制着KUPC国家的降雨量。 KUPC国家是 它被分为 N 区域,Shieru必须让每个区域的降雨均匀。 Shieru施展咒语,让天下雨。 咒语是 M 有不同的类型,每种 它们的编号最大为 1 到 M 。 i 第二个法术有一个潮湿的区域。 a_i 和干旱地区 指定 b_i , a_i 地区有雨。 2 下车,b_i 地区没有下雨, 除此之外 N-2 部分地区有雨 1 秋天。 另外, 执行第i 个咒语 需要 d_i 天。
首先, K 法术 (c_1,...,c_{K}) 被执行。
希鲁就是那个
在执行 K 法术后,你想要执行几个法术来均衡每个区域的总降雨量。
执行
K 咒语后,打印均衡每个区域总降雨量所需的最少天数。
然而,如果不可能使每个地区的总降雨量相等, -1 。
它是一个
入力形式
测试用例按以下格式给出。
N M K
c_1 … c_{K}
a_1 b_1 d_1
…
a_M b_{M} d_M
出力形式
输出是一个表示最小天数的整数,或者 -1 的,
仅由1 行组成。
制約
- 2 \leq N \leq 10000
- 1 \leq M \leq 20000
- 1 \leq K \leq 15
- 1 \leq c_i \leq M
- 1 \leq a_i \leq N
- 1 \leq b_i \leq N
- a_i \neq b_i
- 1 \leq d_i \leq 3
- 所有输入值都是整数。
针对该问题的判断设置了一组30分的测试用例。除了上述约束之外,该组中包含的测试用例还满足以下约束。 通过执行
- K = 1
入出力例
入力例1
9 10 4 1 2 4 6 1 2 1 2 3 2 3 4 3 4 5 1 5 1 2 6 7 3 7 8 2 8 6 3 8 9 1 9 6 1
出力例1
9
3,5,7,9,10咒语,你可以在9天内使每个区域降下相同数量的降雨。
入力例2
3 3 1 1 1 2 1 1 3 2 2 3 3
出力例2
-1
入力例3
2 2 2 1 1 1 2 2 2 1 3
出力例3
6
入力例4
2 2 2 1 2 1 2 2 2 1 3
出力例4
0
入力例5
4 5 2 1 2 2 1 1 4 3 1 1 2 2 1 4 3 3 2 3
出力例5
6