CF958C1.Encryption (easy)

Rebel spy Heidi has just obtained the plans for the Death Star from the Empire and, now on her way to safety, she is trying to break the encryption of the plans (of course they are encrypted – the Empire may be evil, but it is not stupid!). The encryption has several levels of security, and here is how the first one looks.

Heidi is presented with a screen that shows her a sequence of integers A and a positive integer p. She knows that the encryption code is a single number S, which is defined as follows:

Define the score of X to be the sum of the elements of X modulo p.

Heidi is given a sequence A that consists of N integers, and also given an integer p. She needs to split A into 2 parts such that:

• Each part contains at least 1 element of A, and each part consists of contiguous elements of A.
• The two parts do not overlap.
• The total sum S of the scores of those two parts is maximized. This is the encryption code.

Output the sum S, which is the encryption code.

反叛间谍海蒂刚刚从银河帝国手中获取了死星的设计图，如今正赶往安全地点。她正试图破解设计图的加密（当然，设计图是经过加密的——帝国虽邪恶，却并不愚蠢！）。该加密系统有多重安全级别，而第一级加密如下所示。

海蒂面对一个屏幕，屏幕上显示一个整数序列 $A$ 和一个正整数 $p$。她知道加密密钥是一个单独的数字 $S$，其定义如下：

定义子序列 $X$ 的得分为 $X$ 中所有元素之和对 $p$ 取模的结果。

海蒂被给定一个由 $N$ 个整数组成的序列 $A$，以及一个整数 $p$。她需要将 $A$ 恰好划分为 2 个部分，满足以下条件：

• 每一部分至少包含 $A$ 中的一个元素，且每一部分均由 $A$ 中连续的元素构成；
• 这两部分互不重叠；
• 这两部分的得分之和 $S$ 达到最大值。该最大值 $S$ 即为加密密钥。

请输出该和 $S$，即加密密钥。

The first line of the input contains two space-separated integer N and p (2 ≤ N ≤ 100 000, 2 ≤ p ≤ 10 000) – the number of elements in A, and the modulo for computing scores, respectively.

The second line contains N space-separated integers which are the elements of A. Each integer is from the interval [1, 1 000 000].

输入的第一行包含两个以空格分隔的整数 $N$ 和 $p$（$2 \leq N \leq 100\,000$，$2 \leq p \leq 10\,000$）——分别表示数组 $A$ 的元素个数以及计算得分时所用的模数。

第二行包含 $N$ 个以空格分隔的整数，即数组 $A$ 的元素。每个整数均在区间 $[1,\,1\,000\,000]$ 内。

Output the number S as described in the problem statement.

输出问题描述中所述的数 S。

In the first example, the score is maximized if the input sequence is split into two parts as (3, 4), (7, 2). It gives the total score of .

In the second example, the score is maximized if the first part consists of the first three elements, and the second part consists of the rest. Then, the score is .

在第一个例子中，若将输入序列划分为两部分 $(3,\,4)$ 和 $(7,\,2)$，则得分最大，总得分为 。

在第二个例子中，若第一部分包含前三个元素，第二部分包含其余元素，则得分最大，此时得分为 。