Description

灵梦当前拥有的樱点可以使用一个变量 $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）。

现在需要求出，在最优的选择下，灵梦最多可以达成多少个要求。

Input Format

• 第一行共有三个整数 $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$ 关可以获得的樱点个数。

Output Format

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

4 3 2
1 3 4
1 1 2 1

1

Hint

样例 $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$ 序列递增。