← 返回题目列表

AtCoder · abc419_e

H. 子数组和整除性

中文机器翻译题面 查看原题

分数: 475 点

问题陈述

给你一个长度-N 整数序列 A = (A_1, A_2, \ldots, A_N).

您的目标是重复执行以下操作,以便对于每个长度 -L 的连续子数组 A,总和是的倍数 M.

  • 选择一个整数 i 这样 1 \leq i \leq N,并增加值 A_i by 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,两次选择 i = 3,一旦选择 i = 4,你得到 A = (4, 3, 3, 4) 总共有四次操作,其中每个长度-3 连续子数组的总和为 5.


示例输入 2

7 10 4
7 0 9 1 6 4 2

示例输出 2

10