题目内容

机房值班盯盘要复盘一条按小时记下的负载得分。容量评估规定：每个固定长度的复盘窗口，负载之和必须能被容量档整除，否则这条时间线不能过审。盯盘同学只能把某些小时的得分往上调，并且要让总上调量尽量小。

共有 $k$ 个小时，现有得分是 $v_1,v_2,\dots,v_k$。上调后的得分记为 $u_1,u_2,\dots,u_k$，必须满足 $u_i \ge v_i$。复盘窗口长度是 $w$，容量档是 $q$。对每一个起点 $p$（$1 \le p \le k-w+1$），都要有

$\bigl(u_p+u_{p+1}+\cdots+u_{p+w-1}\bigr)\bmod q=0$。

在所有合法的 $u$ 里，请计算 $\sum_{i=1}^{k}(u_i-v_i)$ 的最小值。

注意：输入保证 $0 \le v_i < q$，但构造出的 $u_i$ 不必再落在这个范围内。

小时数和容量档满足 $1 \le k,q \le 5 \times 10^2$，窗长满足 $1 \le w \le k$。

输入描述

第一行三个正整数 $k$、$q$、$w$（$1 \le k,q \le 5 \times 10^2$，$1 \le w \le k$），表示小时数、容量档和复盘窗口长度。

第二行 $k$ 个整数 $v_1,v_2,\dots,v_k$（$0 \le v_i < q$），表示现有小时负载得分。

输出描述

输出一个整数，即最少还要上调的得分总和。

样例1

输入

3 4 2
1 1 1

输出

2

说明

两个窗口原来的和都是 2，要变成 4 的倍数。一种办法是调成 $1,3,1$，两个窗口和都是 4，一共只上调了 2。

样例2

输入

1 3 1
0

输出

0

说明

只有一个小时、窗长为 1，得分 0 已经能被 3 整除，不用上调。

样例3

输入

4 6 2
1 2 3 4

输出

8

说明

一种最优构造是 $4,2,4,8$。三个窗口的和分别是 6、6、12，都能被 6 整除，总上调量为 8。