K. Divide the Sequence (hard version)
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The only difference between the easy and hard versions is the different restrictions on $$$n,\sum |a|,x$$$.

Given a sequence $$$a$$$ of length $$$n$$$ and an integer $$$x$$$, you need to partition the sequence into disjoint $$$k$$$ segments. We call these $$$k$$$ segments $$$[[l_1,r_1],[l_2,r_2],\dots,[l_k,r_k]]$$$ and the division needs to satisfy $$$l_1=1,r_k=n,r_i=l_{i+1}-1(i \lt k)$$$.

Please find the minimum value of $$$\sum_{idx=1}^k\sum_{i={l_{idx}}}^{r_{idx}}\sum_{j=i}^{r_{idx}}[(\sum_{s=i}^{j}a_s)=x]$$$, i.e., the minimum of the sum of the number of subsections of each segment of the division that sums to $$$x$$$.

$$$[expr]$$$ represents the boolean value of the expression $$$expr$$$, i.e., $$$[expr]=1$$$ if $$$expr$$$ is true; otherwise, $$$[expr]=0$$$.

A subsegment of a sequence $$$a_1,a_2,\dots,a_n$$$ is the existence of two subscripts $$$l,r$$$ satisfying $$$1\le l\le r\le n$$$, then $$$[a_l,a_{l+1},\dots,a_r]$$$ is a subsegment of the sequence, and $$$\sum_{i=l}^{r}a_i$$$ is the sum of the subsegments.

Input

In the first line, two integers $$$n,k,x(1\le n\le 10^5;1\le k\le\min(20,n);|x|\le 10^7)$$$, representing the length of the sequence, the number of segments dividing the sequence, and the value of the integer $$$x$$$, respectively.

In the second line, a sequence $$$a$$$ of length $$$n$$$, where $$$|a_i|\le 10^5$$$.

Extra restrictions for the hard version: guarantee $$$\sum_{i=1}^n |a_i|\le 10^7$$$.

Output

Outputs an integer representing the minimum of the sum of the number of sub-segments of each segment of the division that sums to $$$x$$$ across all division schemes.

Examples
Input
4 2 2
2 2 -2 0
Output
2
Input
9 3 0
0 -1 -1 1 -1 1 1 -1 -1
Output
3
Input
1 1 3000
3000
Output
1
Input
6 2 -2
2 3 2 -1 0 3
Output
0
Note

In the first set of samples, take the following division $$$[[1,1],[2,4]]$$$ and the answer is $$$1+1=2$$$.

In the second set of samples, take the following division $$$[[1,5],[6,7],[8,9]]$$$ and the answer is $$$3+0+0=3$$$.