← 返回题目列表

Codeforces · 958/C2

C2. 加密(中)

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

海蒂现在已经破解了死星计划的第一级加密,并盯着屏幕,屏幕上显示着她必须输入的下一个代码的描述。它看起来与第一个惊人地相似——帝国工程师似乎很懒……

Heidi 再次被赋予序列 A,但现在她还被赋予两个整数 k 和 p。她需要找出加密密钥S是什么。

设 X 为整数序列,p 为正整数。我们将 X 的分数定义为 X 模 p 的元素之和。

给 Heidi 一个由 N 个整数组成的序列 A,并且还给定整数 k 和 p。她的目标是将 A 分成 k 部分,这样:

- 每个部分至少包含 A 的 1 个元素,并且每个部分由 A 的连续元素组成。
- 没有两个部分重叠。
- 这些部分的分数总和 S 被最大化。

输出总和S – 加密代码。

输入

输入的第一行包含三个空格分隔的整数 N、k 和 p (k ≤ N ≤ 20 000, 2 ≤ k ≤ 50, 2 ≤ p ≤ 100) – 分别是 A 中的元素数量、A 应分为的部分数量以及计算分数的模数。

第二行包含 N 个空格分隔的整数,它们是 A 的元素。每个整数都来自区间 [1, 1 000 000]。

输出

按照问题陈述中的描述输出数字 S。

示例

输入 #1

4 3 10
3 4 7 2

输出 #1

16

输入 #2

10 5 12
16 3 24 13 9 8 7 5 12 12

输出 #2

37

注意

在第一个示例中,如果输入序列被分割为 (3, 4), (7), (2),则总分将为 $$( 3 + 4 \mod 10 ) + ( 7 \mod 10 ) + ( 2 \mod 10 ) = 7 + 7 + 2 = 16$$。很容易看出这个分数是最大的。

在第二个示例中,获得分数 37 的一种可能方法是进行以下划分:(16, 3, 24), (13, 9), (8), (7), (5, 12, 12)。