「Wdoi-5」樱点收集

119 季 5 月，明明本应是樱花盛开的春天，幻想乡却依然下着大雪。异变的主谋**西行寺幽幽子**在古书上看到，只要使妖樱西行妖满开便会有什么人复活，便出于兴趣命令妖梦收集幻想乡中的春度，一手策划成了这场异变。在收集春度的过程中散落的能量在西行妖的影响下化为**樱点**，散落在幻想乡各处。 出发解决**春雪异变**的灵梦将前往冥界旅途划分为了若干段，每一段都可以收集到一定的樱点。收集齐一定程度的樱点，就会立即开出樱之结界。开出樱之结界后可以短暂地屏蔽一切攻击，并且获得相应的增益。 但是樱之结界何时开放仅由樱点的收集情况所决定，她不得不对樱点进行「规划」。通过某些途径规避某一段路上樱点的收集，借此使得在将来的某几段路程里，灵梦得以恰好在该段的末尾开放樱之结界。 但是现实往往不尽人意。也就是说，可能有某些要求无法达成。灵梦希望找出一个方案，使得她可以达成的要求最多。灵梦委托八云紫帮忙决策，于是这个重任就被一条懒紫交给了式神八云蓝。尽管八云蓝擅长计算，但是八云紫睡觉去了没有给她编程，因而现在这个任务就落到了你的手上。

灵梦当前拥有的樱点可以使用一个**变量** $c$ 存储，初始时为 $0$。当樱点在某个瞬间**恰好**变为了 $k$，灵梦就会展开樱之结界，同时 $c$ 变为 $0$。 现在她把路程**依次**划分为了 $n$ 个关卡，其中第 $i$ 关上，灵梦一共可以获得 $a_i$ 点樱点。这些樱点是均匀分布在这关的路程上的。也就是说，随着这段路程的进行，灵梦的樱点个数会依次增加，每次增加 $1$ 个单位（$c\gets c+1$），恰好在这段路程结束的瞬间会收集到这关中第 $a_i$ 点樱点。  **【需要注意的是，这只是图示参考，不满足实际的数据限制。】** 在这个例子里，灵梦将路径划分为了四个关卡。这四个关卡的樱点个数分别为 $2,0,3,1$。 灵梦提出了 $m$ 个要求。第 $i$ 个要求 $b_i$ 表示灵梦希望在第 $b_i$ 段路程结束的瞬间，**恰好**展开樱之结界（如果在这段路程的中途展开但是结束的瞬间没有展开，那就不算达成了要求）。 灵梦可以选择在某个关卡开头放 bomb，**跳过**整个关卡的樱点收集。这样的机会**有且仅有**一次（当然，灵梦可以选择不使用 bomb）。 现在需要求出，在最优的选择下，灵梦**最多**可以达成多少个要求。

- 第一行共有三个整数 $n,m,k$，分别表示关卡数、要求个数，以及常量 $k$。 - 第二行 $m$ 个整数 $b_1,b_2,\cdots b_m$，描述了灵梦的 $m$ 个要求。**保证 $\bm{b_i}$ 单调递增**。 - 第三行 $n$ 个整数 $a_1,a_2,\cdots a_n$，描述了第 $i$ 关可以获得的樱点个数。

- 共一行一个整数，表示答案。

4 3 2
1 3 4
1 1 2 1

1

样例 $2$ 见下发的附件 $\textbf{\textit{sukura2.in/sakura2.ans}}$。该样例约束与测试点 $1\sim 8$ 一致。 样例 $3$ 见下发的附件 $\textbf{\textit{sukura3.in/sakura3.ans}}$。该样例约束与测试点 $9\sim 14$ 一致。 样例 $4$ 见下发的附件 $\textbf{\textit{sukura4.in/sakura4.ans}}$。该样例约束与测试点 $15\sim 20$ 一致。 #### 样例 1 解释 - 在不使用 bomb 时，灵梦会在第 $2$、$3$ 关开出樱之结界，其中第 $3$ 关在统计序列中，满足要求数为 $1$。 - 在第 $1$ 关使用 bomb，灵梦会在第 $4$ 关开出樱之结界，且第 $4$ 关在统计序列中，满足要求数为 $1$。 - 在第 $2$ 关使用 bomb，灵梦会在第 $4$ 关开出樱之结界，且第 $4$ 关在统计序列中，满足要求数为 $1$。 - 在第 $3$ 关使用 bomb，灵梦会在第 $2$ 关开出樱之结界，且第 $2$ 关不在统计序列中，满足要求数为 $0$。 - 在第 $4$ 关使用 bomb，灵梦会在第 $2$、$3$ 关开出樱之结界，其中第 $3$ 关在序列中，满足要求数为 $1$。 #### 数据范围及约定 本题共有 $20$ 个测试点，每个测试点 $5$ 分。最终分数为所有测试点分数之和。 $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Task} & \bm{n\le } & \bm{k\le} \cr\hline 1\sim 8 & 200 & 10^3 \cr\hline 9\sim 14 & 2\times 10^3 & 10^5 \cr\hline 15\sim 20 & 3\times 10^5 & 10^6 \cr\hline \end{array} $$ 对于 $100\%$ 的数据，保证 $1\le m\le n\le 3\times 10^5$，$1\le k\le 10^6$，$1\le a_i\le 10^9$，$1 \le b_i \le n$，$b$ 序列递增。