题目描述

你和朋友参加酒馆的知识问答活动。活动共有 $N$ 道题，必须按顺序逐题作答。第 $i$ 道题答对可以获得 $points_i$ 分，答错则扣除 $points_i$ 分。

每答对一道题，你还会得到一枚代币。当持有的代币数达到 $K$ 时，酒馆会立即收走全部代币，并额外奖励 $bonuses_i$ 分，其中 $i$ 是刚刚答完的题目编号。如果答错一道题，酒馆也会收走你持有的全部代币，但不给予奖励。在整个活动中，你可以多次获得奖励。

最初你的得分和代币数都是 $0$。你知道所有题目的答案，可以自由选择每道题答对还是故意答错。你必须回答全部题目，不能跳过。请计算最终能够获得的最大得分。

为了缩短输入，数组 $points$ 和 $bonuses$ 分别由种子数组 $p$、$b$ 生成。对一个种子数组 $X$，使用下面的过程生成长度为 $N$ 的数组 $P$。伪代码中的数组下标从 $0$ 开始。

k = 0
M = X 的长度
for i = 0, 1, ..., N-1:
    P[i] = X[k]
    s = (k + 1) % M
    X[k] = ((X[k] ^ X[s]) + 13) % G
    k = s

其中 % 表示取模，^ 表示按位异或。赋值右侧使用赋值前的数组元素值；若 $M=1$，则参与异或的两个值为同一个值。

使用 $p$ 作为 $X$、$G=1001$ 生成 $points$；独立地使用 $b$ 作为 $X$、$G=10001$ 生成 $bonuses$。生成过程中种子数组会被原地修改。输入编码仅用于缩短输入，解题不需要利用生成器的特殊性质。

输入格式

第一行包含四个整数 $N,K,A,B$，分别表示题目数量、兑换奖励所需的代币数，以及种子数组 $p$、$b$ 的长度。

第二行包含 $A$ 个整数，表示 $p$。

第三行包含 $B$ 个整数，表示 $b$。

输出格式

输出一个整数，表示最终能够获得的最大得分。答案可能超过 32 位有符号整数的范围。

样例 1

5 5 5 5
1 2 3 4 5
0 0 0 2 5

20

样例 2

5 3 5 5
1 2 3 4 5
0 0 0 2 5

16

样例 3

5 3 3 2
1 2 3
7 0

98

数据范围

• $1\le N,K\le500000$；
• $1\le A,B\le50$；
• $0\le p_i\le1000$；
• $0\le b_i\le10000$。

样例说明

样例 1 中，五道题全部答对，获得 $15$ 分答题得分和 $5$ 分额外奖励，最终得到 $20$ 分。

样例 2 中，只有第二道题故意答错，其余题全部答对；最后三道题连续答对，在第五题获得奖励，最终得到 $16$ 分。

样例 3 生成的题目分值为 $1,2,3,16,14$，奖励分值为 $7,0,20,33,66$。