#P18293. Knights of Night

Knights of Night

Knights of Night

有两组骑士,每组各有 nn 人。第一组第 ii 人的力量为 aia_i,第二组第 jj 人的力量为 bjb_j。

一场战斗由两组中各选一人参加,每名骑士最多参加一场战斗。第一组第 ii 人与第二组第 jj 人战斗的疯狂值为

(ai+bj) mod 998244353.(a_i+b_j)\bmod 998244353.

另外有 mm 对骑士禁止互相战斗。

对每个 x=1,2,…,kx=1,2,\ldots,k,分别求出恰好安排 xx 场战斗时,所有战斗的疯狂值之和的最大值。若无法安排恰好 xx 场战斗,输出 −1-1。

取模只作用于单场战斗。多场战斗的疯狂值之和不取模,可以超过 998244353998244353。各个 xx 的安排分别优化,不要求小规模的最优安排是大规模最优安排的一部分。

输入格式

只有一组数据。

第一行包含三个整数 n,m,kn,m,k,满足

$$1\le n\le 10^5,\qquad 0\le m\le 3\times 10^5,\qquad 1\le k\le \min(n,200).$$

第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n。

第三行包含 nn 个整数 b1,…,bnb_1,\ldots,b_n。

所有力量均满足 0≤ai,bj<9982443530\le a_i,b_j<998244353。

接下来 mm 行,每行包含两个整数 ui,viu_i,v_i,表示第一组第 uiu_i 人与第二组第 viv_i 人之间的战斗被禁止。其中 1≤ui,vi≤n1\le u_i,v_i\le n,保证所有给出的有序对 (ui,vi)(u_i,v_i) 互不相同。两组的编号各自独立,因此 ui=viu_i=v_i 的禁战对也是合法的。

输出格式

输出一行 kk 个整数。第 xx 个整数是恰好安排 xx 场战斗的最大疯狂值之和,或者在无法安排时输出 −1-1。

样例

样例 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