Yet Another Jellyfish and Mex

You are given an array of $$$n$$$ nonnegative integers $$$a_1, a_2, \dots, a_n$$$, satisfying $$$\max(a) < m$$$.

Let $$$v$$$ be a variable that is initialized to $$$0$$$, Jellyfish will perform the following operation until $$$a$$$ is empty:

• Select a number $$$z$$$ satisfying $$$1 \leq z \leq k$$$ and select $$$z$$$ indices $$$i_1, i_2, \dots, i_z$$$ ($$$1 \leq i_1 < i_2 < ... < i_z \leq |a|$$$), then delete $$$a_{i_1}, a_{i_2}, \dots, a_{i_z}$$$ from $$$a$$$.
• add $$$\operatorname{MEX}(a)^{\dagger}$$$ to $$$v$$$.

Now Jellyfish wants to know the minimum possible final value of $$$v$$$ if he performs all the operations optimally.

$$$^{\dagger}$$$ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

• The MEX of $$$[2,2,1]$$$ is $$$0$$$, because $$$0$$$ does not belong to the array.
• The MEX of $$$[3,1,0,1]$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ belong to the array, but $$$2$$$ does not.
• The MEX of $$$[0,3,1,2]$$$ is $$$4$$$ because $$$0$$$, $$$1$$$, $$$2$$$, and $$$3$$$ belong to the array, but $$$4$$$ does not.

Input

The first line of each test contains three single integers $$$n\ (m \leq n \leq 10^8), m(1 \leq m \leq 2 \times 10^5), k(1 \leq k \leq 500)$$$.

Due to excessive input volume, we do not directly input $$$a$$$, but for each $$$x (0 \leq x < m)$$$, input the number of occurrences of $$$x$$$ in $$$a$$$.

The next line contains $$$m$$$ numbers $$$c_1, c_2, \dots, c_{m-1}\ (0 \leq c_i \leq n, \sum_{i=1}^n{c_i}=n)$$$. — the number of occurrences of $$$x$$$ in $$$a$$$.

It can prove that the order of the values is not important in $$$a$$$.

Output

Output a single integer. — the minimum possible final value of $$$v$$$.

Similar to the tutorial of 1875D - Jellyfish and Mex, We only care about the operation before $$$\text{MEX}(a)$$$ reaches $$$0$$$.

By using greedy we know that each time we should try to delete as many numbers as possible, which means every time we will delete $$$\min(|a|, k)$$$ values of $$$a$$$.

Lemma1. If $$$i < j$$$ and $$$c_i \leq c_j$$$, we won't delete $$$j$$$ from $$$a$$$.

Proof. Similar to the tutorial of 1875D - Jellyfish and Mex, if we have deleted $$$j$$$, we will delete all of $$$j$$$ in $$$a$$$, then make $$$\text{MEX}(a)$$$ to $$$j$$$, but because $$$c_i \leq c_j$$$, we can delete all of $$$i$$$ instead of $$$j$$$ in the same number of operations, but the $$$\text{MEX}(a)$$$ will become $$$i$$$, which is better than $$$j$$$.

Because $$$1 + 2 + \dots + \sqrt{2n} > n$$$, and according to Lemma1, there will be only $$$\min(\sqrt{2n}, m)$$$ possible values we will delete.

Lemma2. Every operation, there are at most two values of numbers we will delete. And if we delete two values of numbers, let's call them $$$x$$$ and $$$y$$$ $$$(x < y)$$$. We will delete all of $$$y$$$, and we can't delete all of $$$x$$$ in the operation.

Proof. For each operation, if we delete all the numbers of value $$$x$$$, we will have no need to delete $$$y$$$ satisfying $$$x < y$$$, because we have removed all of $$$x$$$, so $$$y$$$ will no longer have an effect on $$$\text{MEX}(a)$$$. And also, let's consider the next value of $$$\text{MEX}(a)$$$ after this operation, let's call it $$$x'$$$, except the value of the $$$\text{MEX}(a)$$$ after this operation, We won't delete other values except $$$x'$$$, because the deletion of these numbers can be delay to the operations after $$$\text{MEX}(a)$$$ reaches $$$x'$$$.

Now we can use dynamic programming to solve the problem. Let's define $$$dp(i, x)$$$ means the $$$\text{MEX}(a)$$$ after next operation will be $$$i$$$, and the number of $$$i$$$ in $$$a$$$ is $$$x$$$. We can't enumerate directly for transition, it's $$$O(\min(n, m^2) \times k)$$$, so we can use Convex Hull Optimisation to solve this problem. for each $$$x$$$, we build a convex of $$$(i, dp(i, x))$$$, Since both $$$c_i$$$ and $$$i$$$ are monotone while transiting, so we can use two pointers instead of binary searching.

Time complexity: $$$O(\min(\sqrt n, m) \times k)$$$

Memory complexity: $$$O(\min(\sqrt n, m) \times k)$$$