海蒂现在只差一个密码就能破解死星计划的加密。应该向她展示下一个代码描述的屏幕看起来和上一个几乎一样,但谁能想到邪恶的帝国工程师会在这个小屏幕上填满几百万位数字!认为有人会读完它们真是太荒谬了……
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 ≤ 500 000, 2 ≤ k ≤ 100, 2 ≤ p ≤ 100) – 分别是 A 中的元素数量、A 应分为的部分数量以及计算分数的模数。
第二行包含 N 个空格分隔的整数,它们是 A 的元素。每个整数都来自区间 [1, 1 000 000]。
输出
按照问题陈述中的描述输出数字 S。
示例
输入 #1
4 3 10 3 4 7 2
输出 #1
6
输入 #2
10 5 12 16 3 24 13 9 8 7 5 12 12
输出 #2
13
注意
在第一个示例中,如果输入序列被分割为 (3), (4, 7), (2),则总分将为 $$( 3 \bmod { 1 0 } ) + ( 4 + 7 \bmod { 1 0 } ) + ( 2 \bmod { 1 0 } ) = 3 + 1 + 2 = 6$$。很容易看出这个分数是可能的最小分数。
在第二个示例中,获得分数 13 的一种可能方法是进行以下分割:(16, 3), (24), (13), (9, 8), (7, 5, 12, 12)。