Background

In May of Season 119, when it should have been the spring with cherry blossoms in full bloom, Gensokyo was still covered by heavy snow. The mastermind behind this incident, Saigyouji Yuyuko, read in an ancient book that if the youkai cherry tree Saigyou Ayakashi reached full bloom, someone would be revived. Out of curiosity, she ordered Youmu to collect spring power from Gensokyo, and personally planned this incident. During the collection of spring power, the scattered energy, under the influence of Saigyou Ayakashi, turned into sakura points, scattered all over Gensokyo.

Reimu, who set out to resolve the Spring Snow Incident, divided her journey to the Netherworld into several segments. In each segment, she can collect a certain number of sakura points. Once she collects enough sakura points, a Cherry Blossom Barrier will immediately be activated. After activating the barrier, she can briefly block all attacks and gain corresponding buffs.

However, when the Cherry Blossom Barrier activates is determined only by how sakura points are collected, so she has to "plan" the sakura points. By some means, she can avoid collecting sakura points on some segment, so that in some future segments, Reimu can activate the Cherry Blossom Barrier exactly at the end of that segment.

But reality is often not ideal. That is, some requirements may not be achievable. Reimu wants to find a plan that lets her satisfy as many requirements as possible. Reimu asked Yukari Yakumo for help, but this heavy responsibility was handed by a lazy Yukari to her shikigami, Ran Yakumo. Although Ran Yakumo is good at calculation, Yukari went to sleep and did not write code for her, so now this task falls to you.

Problem Description

Reimu’s current number of sakura points can be stored in a variable $c$, initially $0$. When at some moment the sakura points become exactly $k$, Reimu will activate the Cherry Blossom Barrier, and at the same time $c$ becomes $0$.

Now she divides the journey in order into $n$ stages. In stage $i$, Reimu can obtain a total of $a_i$ sakura points. These sakura points are evenly distributed along the route of this stage. That is, as this segment proceeds, Reimu’s sakura points will increase one by one, each time increasing by $1$ unit ($c\gets c+1$). Exactly at the moment this segment ends, she will collect the $a_i$-th sakura point of this stage.

[Note that this is only an illustration reference and does not satisfy the actual constraints.]

In this example, Reimu divides the path into four stages. The numbers of sakura points in these four stages are $2,0,3,1$.

Reimu提出了 $m$ 个要求。The $i$-th requirement $b_i$ means that Reimu wants to activate the Cherry Blossom Barrier exactly at the moment the $b_i$-th segment ends (if it activates in the middle of this segment but is not activated at the ending moment, it does not count as satisfying the requirement).

Reimu may choose to place a bomb at the beginning of some stage to skip collecting sakura points for the entire stage. This opportunity exists exactly once (of course, Reimu may choose not to use the bomb).

Now you need to find, under the best choice, the maximum number of requirements Reimu can satisfy.

Input Format

• The first line contains three integers $n,m,k$, representing the number of stages, the number of requirements, and the constant $k$.
• The second line contains $m$ integers $b_1,b_2,\cdots b_m$, describing Reimu’s $m$ requirements. It is guaranteed that $\bm{b_i}$ is non-decreasing.
• The third line contains $n$ integers $a_1,a_2,\cdots a_n$, describing the number of sakura points obtainable in stage $i$.

Output Format

• One line with one integer, representing the answer.

4 3 2
1 3 4
1 1 2 1

1

Hint

Sample $2$ can be found in the attached file $\textbf{\textit{sukura2.in/sakura2.ans}}$. This sample has the same constraints as testdata $1\sim 8$.
Sample $3$ can be found in the attached file $\textbf{\textit{sukura3.in/sakura3.ans}}$. This sample has the same constraints as testdata $9\sim 14$.
Sample $4$ can be found in the attached file $\textbf{\textit{sukura4.in/sakura4.ans}}$. This sample has the same constraints as testdata $15\sim 20$.

Explanation for Sample 1

• Without using a bomb, Reimu will activate the Cherry Blossom Barrier in stages $2$ and $3$. Among them, stage $3$ is in the counted sequence, so the number of satisfied requirements is $1$.
• If she uses a bomb in stage $1$, Reimu will activate the barrier in stage $4$, and stage $4$ is in the counted sequence, so the number of satisfied requirements is $1$.
• If she uses a bomb in stage $2$, Reimu will activate the barrier in stage $4$, and stage $4$ is in the counted sequence, so the number of satisfied requirements is $1$.
• If she uses a bomb in stage $3$, Reimu will activate the barrier in stage $2$, and stage $2$ is not in the counted sequence, so the number of satisfied requirements is $0$.
• If she uses a bomb in stage $4$, Reimu will activate the barrier in stages $2$ and $3$. Among them, stage $3$ is in the sequence, so the number of satisfied requirements is $1$.

Constraints and Notes

This problem has $20$ test points, $5$ points each. The final score is the sum of the scores of all test points.

$$\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}$$

For $100\%$ of the data, it is guaranteed that $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$, and the sequence $b$ is strictly increasing.

Translated by ChatGPT 5