CF1917C Watering an Array

你有一个长度为 $n$ 的整数数组 $a_1, a_2, \ldots, a_n$。在接下来的 $d$ 天里，你每天必须执行以下两种操作之一： - 对数组 $a$ 的前 $b_i$ 个元素各加 $1$（即对每个 $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$ 天结束时，你最多能获得多少分？ 由于 $d$ 可能很大，序列 $b$ 以压缩格式给出： - 给定一个长度为 $k$ 的整数序列 $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$ 天结束时你能获得的最大得分。

在第一个测试用例中，序列 $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$ 天执行第二种操作。 由 ChatGPT 4.1 翻译