CF958C1 Encryption (easy)

反叛间谍 Heidi 刚刚从帝国手中获得了死星的设计图，现在她正在逃往安全地带，并试图破解设计图的加密（当然这些设计图是加密的——帝国也许很邪恶，但并不愚蠢！）。加密有多层安全措施，第一层如下所示。 Heidi 面前的屏幕上显示着一个整数序列 $A$ 和一个正整数 $p$。她知道加密代码是一个数字 $S$，其定义如下： 定义 $X$ 的得分为 $X$ 所有元素之和对 $p$ 取模的结果。 Heidi 得到一个包含 $N$ 个整数的序列 $A$，以及一个整数 $p$。她需要将 $A$ 分成两部分，使得： - 每一部分都至少包含 $A$ 的一个元素，并且每一部分都由 $A$ 的连续元素组成。 - 两部分不重叠。 - 这两部分得分之和 $S$ 最大。这个 $S$ 就是加密代码。 请输出 $S$ 的最大值，即加密代码。

第一行包含两个用空格分隔的整数 $N$ 和 $p$（$2 \leq N \leq 100000$，$2 \leq p \leq 10000$）——表示 $A$ 的元素个数，以及用于计算得分的模数。 第二行包含 $N$ 个用空格分隔的整数，表示序列 $A$ 的元素。每个整数都在区间 $[1, 1000000]$ 内。

输出一个整数 $S$，即题目中所述的最大得分。

在第一个样例中，若将输入序列分为 $(3,4)$ 和 $(7,2)$ 两部分，得分最大。总得分为 $((3+4)\bmod 5) + ((7+2)\bmod 5) = 2 + 4 = 6$。 在第二个样例中，若第一部分为前三个元素，第二部分为剩下的元素，则得分为 $((1+2+3)\bmod 4) + ((4+5+6+7)\bmod 4) = 2 + 2 = 4$。 由 ChatGPT 4.1 翻译