你有一个整数数组$$$a_1, a_2, \ldots, a_n$$$,长度为$$$n$$$。在接下来的 $$$d$$$ 天的第 $$$i$$$ 日,您将执行以下两个操作之一:
- 将 $$$1$$$ 添加到数组 $$$a$$$ 的前 $$$b_i$$$ 元素中(即,为每个 $$$1 \le j \le b_i$$$ 设置 $$$a_j := a_j + 1$$$)。
- 计算等于其位置的元素(即 $$$a_j = j$$$)。将此类元素的数量表示为 $$$c$$$。然后,将 $$$c$$$ 添加到分数中,并将整个数组 $$$a$$$ 重置为长度为 $$$n$$$ 的 $$$0$$$ 数组(即设置 $$$[a_1, a_2, \ldots, a_n] := [0, 0, \ldots, 0]$$$)。
你的分数一开始等于$$$0$$$。请注意,每天您应该执行上述操作之一:您不能跳过一天或在同一天执行这两个操作。
你最终能获得的最高分数是多少?
由于 $$$d$$$ 可能非常大,因此序列 $$$b$$$ 以压缩格式提供给您:
- 给你一个整数序列 $$$v_1, v_2, \ldots, v_k$$$。序列 $$$b$$$ 是 $$$v$$$ 的无限多个副本的串联: $$$b = [v_1, v_2, \ldots, v_k, v_1, v_2, \ldots, v_k, \ldots]$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试用例的数量。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$d$$$ ($$$1 \le n \le 2000$$$, $$$1 \le k \le 10^5$$$, $$$k \le d \le 10^9$$$) — 数组 $$$a$$$ 的长度,序列 $$$v$$$ 的长度以及您要执行操作的天数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$) — 数组 $$$a$$$。
每个测试用例的第三行包含 $$$k$$$ 整数 $$$v_1, v_2, \ldots, v_k$$$ ($$$1 \le v_i \le n$$$) - 序列 $$$v$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$,所有测试用例的 $$$k$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出一个整数:您在第 $$$d$$$ 天结束时可以获得的最高分数。
示例
输入 #1
5 3 4 4 1 2 3 1 3 2 3 6 2 3 6 1 2 4 1 5 6 6 5 1 1 0 5 0 5 0 5 1 1 1 1 1 3 4 6 1 2 3 1 3 2 3
输出 #1
4 3 0 1 5
注意
在第一个测试用例中,序列 $$$b$$$ 等于 $$$[1, 3, 2, 3, 1, 3, 2, 3, \ldots]$$$,这种情况的最佳解决方案之一如下:
- 在$$$1$$$第一天执行第二种类型的操作:你的分数增加$$$3$$$,并且数组$$$a$$$变得等于$$$[0, 0, 0]$$$。
- 在$$$2$$$第一天执行第一种类型的操作:数组$$$a$$$ 变得等于$$$[1, 1, 1]$$$。
- 在第 $$$3$$$ 天执行第一种类型的操作:数组 $$$a$$$ 变得等于 $$$[2, 2, 1]$$$。
- 在第 $$$4$$$ 天执行第二种操作:你的分数增加 $$$1$$$,数组 $$$a$$$ 变为等于 $$$[0, 0, 0]$$$。
可以证明得分不可能超过$$$4$$$,所以答案是$$$4$$$。
在第二个测试用例中,序列 $$$b$$$ 等于 $$$[6, 6, 6, 6, \ldots]$$$。获得$$$3$$$评分的方法之一是在第$$$1$$$日和第$$$3$$$日执行第一类型的操作,并在第$$$2$$$日执行第二类型的操作。