「Wdoi-5」樱点收集
题目背景
119 季 5 月,明明本应是樱花盛开的春天,幻想乡却依然下着大雪。异变的主谋**西行寺幽幽子**在古书上看到,只要使妖樱西行妖满开便会有什么人复活,便出于兴趣命令妖梦收集幻想乡中的春度,一手策划成了这场异变。在收集春度的过程中散落的能量在西行妖的影响下化为**樱点**,散落在幻想乡各处。
出发解决**春雪异变**的灵梦将前往冥界旅途划分为了若干段,每一段都可以收集到一定的樱点。收集齐一定程度的樱点,就会立即开出樱之结界。开出樱之结界后可以短暂地屏蔽一切攻击,并且获得相应的增益。
但是樱之结界何时开放仅由樱点的收集情况所决定,她不得不对樱点进行「规划」。通过某些途径规避某一段路上樱点的收集,借此使得在将来的某几段路程里,灵梦得以恰好在该段的末尾开放樱之结界。
但是现实往往不尽人意。也就是说,可能有某些要求无法达成。灵梦希望找出一个方案,使得她可以达成的要求最多。灵梦委托八云紫帮忙决策,于是这个重任就被一条懒紫交给了式神八云蓝。尽管八云蓝擅长计算,但是八云紫睡觉去了没有给她编程,因而现在这个任务就落到了你的手上。
题目描述
灵梦当前拥有的樱点可以使用一个**变量** $c$ 存储,初始时为 $0$。当樱点在某个瞬间**恰好**变为了 $k$,灵梦就会展开樱之结界,同时 $c$ 变为 $0$。
现在她把路程**依次**划分为了 $n$ 个关卡,其中第 $i$ 关上,灵梦一共可以获得 $a_i$ 点樱点。这些樱点是均匀分布在这关的路程上的。也就是说,随着这段路程的进行,灵梦的樱点个数会依次增加,每次增加 $1$ 个单位($c\gets c+1$),恰好在这段路程结束的瞬间会收集到这关中第 $a_i$ 点樱点。
![](https://cdn.luogu.com.cn/upload/image_hosting/3yuiywt0.png)
**【需要注意的是,这只是图示参考,不满足实际的数据限制。】**
在这个例子里,灵梦将路径划分为了四个关卡。这四个关卡的樱点个数分别为 $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$ 关可以获得的樱点个数。
输出格式
- 共一行一个整数,表示答案。
输入输出样例
输入样例 #1
4 3 2
1 3 4
1 1 2 1
输出样例 #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$ 序列递增。