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