#P18293. Knights of Night
Knights of Night
Knights of Night
有两组骑士,每组各有 人。第一组第 人的力量为 ,第二组第 人的力量为 。
一场战斗由两组中各选一人参加,每名骑士最多参加一场战斗。第一组第 人与第二组第 人战斗的疯狂值为
另外有 对骑士禁止互相战斗。
对每个 ,分别求出恰好安排 场战斗时,所有战斗的疯狂值之和的最大值。若无法安排恰好 场战斗,输出 。
取模只作用于单场战斗。多场战斗的疯狂值之和不取模,可以超过 。各个 的安排分别优化,不要求小规模的最优安排是大规模最优安排的一部分。
输入格式
只有一组数据。
第一行包含三个整数 ,满足
$$1\le n\le 10^5,\qquad 0\le m\le 3\times 10^5,\qquad 1\le k\le \min(n,200).$$第二行包含 个整数 。
第三行包含 个整数 。
所有力量均满足 。
接下来 行,每行包含两个整数 ,表示第一组第 人与第二组第 人之间的战斗被禁止。其中 ,保证所有给出的有序对 互不相同。两组的编号各自独立,因此 的禁战对也是合法的。
输出格式
输出一行 个整数。第 个整数是恰好安排 场战斗的最大疯狂值之和,或者在无法安排时输出 。
样例
样例 1
3 4 3
10 998244352 5
998244352 8 6
1 2
1 3
2 2
3 3
998244351 998244364 27
样例 2
6 10 5
749208241 448597025 773867529 808779198 554621438 19807774
281439035 850615248 796547348 327547103 765641981 702406342
1 4
5 3
3 4
2 1
5 6
4 3
6 2
6 3
2 6
2 4
882168541 1667618296 2328768389 2900938913 3354309143
样例 3
1 1 1
0
0
1 1
-1