#519. Nanami and the Last Enigma (hard version)

简单版和困难版的唯一区别在于对于 $n,\sum |a|,x$ 的限制不同。

最终，Nanami 还是来到了医院。

医院的病房排列成了一个长度为 $n$ 的序列，同时每间病房上都写着一个数字 $a$。Nanami给了你一个整数 $x$，你需要把医院的病房划分成不相交的 $k$ 段。称这 $k$ 段为 $[[l_1,r_1],[l_2,r_2],\dots,[l_k,r_k]]$，划分需要满足 $l_1=1,r_k=n,l_i\le r_i,r_i=l_{i+1}-1(i<k)$。

请你求出 $\sum_{idx=1}^k\sum_{i={l_{idx}}}^{r_{idx}}\sum_{j=i}^{r_{idx}}[(\sum_{s=i}^{j}a_s)=x]$ 的最小值，即划分的每段的子段的和为 $x$ 的数量的和的最小值。

$[expr]$ 代表表达式 $expr$ 的布尔值，即如果 $expr$ 为真，则 $[expr]=1$；否则，$[expr]=0$。

一个序列 $a_1,a_2,\dots,a_n$ 的子段是指存在两个下标 $l,r$ 满足 $1\le l\le r\le n$，那么 $[a_l,a_{l+1},\dots,a_r]$ 就是该序列的一个子段，$\sum_{i=l}^{r}a_i$ 就是这个子段的和。

第一行，两个整数 $n,k,x(1\le n\le 10^5;1\le k\le\min(20,n);|x|\le 10^7)$，分别代表序列的长度、划分序列的段数与整数 $x$ 的值。

第二行，一个长度为 $n$ 的序列 $a$，其中 $|a_i|\le 10^5$。

困难版的额外限制：保证 $\sum_{i=1}^n |a_i|\le 10^7$。

输出一个整数，代表在所有的划分方案中，划分的每段的子段的和为 $x$ 的数量的和的最小值。

输入样例

4 2 2
2 2 -2 0

输出样例

2

输入样例

9 3 0
0 -1 -1 1 -1 1 1 -1 -1

输出样例

3

输入样例

1 1 3000
3000

输出样例

1

输入样例

6 2 -2
2 3 2 -1 0 3

输出样例

0

提示

在第一组样例中，采取如下的划分方式 $[[1,1],[2,4]]$，答案为 $1+1=2$。

在第二组样例中，采取如下的划分方式 $[[1,5],[6,7],[8,9]]$，答案为 $3+0+0=3$。