C. Поливка массива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть массив целых чисел $$$a_1, a_2, \ldots, a_n$$$ длины $$$n$$$. В $$$i$$$-й из следующих $$$d$$$ дней вы собираетесь выполнить ровно одно из следующих двух действий:

  • Прибавить $$$1$$$ к каждому из первых $$$b_i$$$ элементов массива $$$a$$$ (т.е. присвоить $$$a_j := a_j + 1$$$ для всех $$$1 \le j \le b_i$$$).
  • Посчитаем количество элементов, которые равны своей позиции (т.е. $$$a_j = j$$$). Обозначим количество таких элементов за $$$c$$$. Затем нужно прибавить $$$c$$$ к своему счету и сбросить весь массив $$$a$$$ к $$$0$$$-массиву длины $$$n$$$ (т.е. присвоить $$$[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$$$-го дня.

Пример
Входные данные
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
Выходные данные
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$$$-й день.