叛军间谍海蒂刚刚从帝国那里获得了死星的设计图,现在正在前往安全的路上,她正试图破解设计图的加密(当然它们是加密的——帝国可能是邪恶的,但它并不愚蠢!)。加密有多个安全级别,以下是第一个级别的外观。
Heidi 看到一个屏幕,其中显示了一系列整数 A 和一个正整数 p。她知道加密代码是单个数字S,其定义如下:
将 X 的分数定义为 X 模 p 的元素之和。
Heidi 被赋予一个由 N 个整数组成的序列 A,并且还被赋予一个整数 p。她需要将 A 分成两部分,以便:
- 每个部分至少包含 A 的 1 个元素,并且每个部分由 A 的连续元素组成。
- 两个部分不重叠。
- 这两个部分的分数总和 S 被最大化。这是加密代码。
输出和S,即加密码。
输入
输入的第一行包含两个空格分隔的整数 N 和 p (2 ≤ N ≤ 100 000, 2 ≤ p ≤ 10 000) – 分别是 A 中的元素数量和计算分数的模数。
第二行包含 N 个空格分隔的整数,它们是 A 的元素。每个整数都来自区间 [1, 1 000 000]。
输出
按照问题陈述中的描述输出数字 S。
示例
输入 #1
4 10 3 4 7 2
输出 #1
16
输入 #2
10 12 16 3 24 13 9 8 7 5 12 12
输出 #2
13
注意
在第一个示例中,如果输入序列分为两部分(3, 4)、(7, 2),则得分最大化。它给出的总分是$$(3+4\mod10)+(7+2\mod10)=16$$。
在第二个示例中,如果第一部分由前三个元素组成,而第二部分由其余元素组成,则得分最高。那么,得分为 $$( 1 6 + 3 + 2 4 \mod 1 2 ) + ( 1 3 + 9 + 8 + 7 + 5 + 1 2 \mod 1 2 ) = 7 + 6 = 1 3$$。