/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 475 点
問題文
長さ N の整数列 A = (A_1, A_2, \ldots, A_N) が与えられます。
あなたの目的は、以下の操作を繰り返し行うことにより、A のすべての長さ L の連続部分列についてその総和が M の倍数であるようにすることです。
- 1 \leq i \leq N なる整数 i を選び、A_i の値を 1 増やす。
目的を達成するまでの操作回数として考えられる最小値を求めてください。
制約
- 1 \leq N, M \leq 500
- 1 \leq L \leq N
- 0 \leq A_i < M
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M L A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
4 5 3 4 2 1 3
出力例 1
4
i = 2 を選ぶ操作を 1 回、i = 3 を選ぶ操作を 2 回、i = 4 を選ぶ操作を 1 回行うことで合計 4 回の操作で A = (4, 3, 3, 4) となり、すべての長さ 3 の連続部分列の総和が 5 の倍数となります。
入力例 2
7 10 4 7 0 9 1 6 4 2
出力例 2
10
Score : 475 points
Problem Statement
You are given a length-N integer sequence A = (A_1, A_2, \ldots, A_N).
Your goal is to perform the following operation repeatedly so that for every length-L contiguous subarray of A, the sum is a multiple of M.
- Choose an integer i such that 1 \leq i \leq N, and increase the value of A_i by 1.
Find the minimum possible number of operations before achieving the goal.
Constraints
- 1 \leq N, M \leq 500
- 1 \leq L \leq N
- 0 \leq A_i < M
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M L A_1 A_2 \ldots A_N
Output
Output the answer.
Sample Input 1
4 5 3 4 2 1 3
Sample Output 1
4
By performing the operation once choosing i = 2, twice choosing i = 3, and once choosing i = 4, you get A = (4, 3, 3, 4) with a total of four operations, where every length-3 contiguous subarray sums to a multiple of 5.
Sample Input 2
7 10 4 7 0 9 1 6 4 2
Sample Output 2
10