암호화 (쉬운 버전)

반란군 첩자 Heidi는 방금 Empire로부터 Death Star의 설계도를 손에 넣었고, 이제 안전한 곳으로 가는 도중에 설계도의 암호를 해독하려 한다(물론 설계도는 암호화되어 있다. Empire가 사악할지는 몰라도 어리석지는 않다!). 암호화에는 여러 보안 단계가 있으며, 첫 번째 단계는 다음과 같다.

Heidi에게 정수 수열 A와 양의 정수 p가 표시된 화면이 주어진다. Heidi는 암호화 코드가 하나의 수 S이며, 다음과 같이 정의된다는 것을 알고 있다:

X의 점수를 X의 원소 합을 p로 나눈 나머지로 정의한다.

Heidi에게 N개의 정수로 이루어진 수열 A와 정수 p가 주어진다. Heidi는 다음 조건을 만족하도록 A를 2개의 부분으로 나누어야 한다:

• 각 부분은 A의 원소를 적어도 1개 포함하며, 각 부분은 A의 연속한 원소들로 이루어진다.
• 두 부분은 겹치지 않는다.
• 두 부분의 점수의 총합 S가 최대가 되어야 한다. 이것이 암호화 코드이다.

암호화 코드인 합 S를 출력한다.

입력의 첫 번째 줄에 공백으로 구분된 두 정수 N와 p (2 ≤ N ≤ 100 000, 2 ≤ p ≤ 10 000)가 주어진다. 각각 A의 원소 수와 점수를 계산할 때 사용하는 모듈로이다.

두 번째 줄에는 A의 원소인, 공백으로 구분된 N개의 정수가 주어진다. 각 정수는 구간 $[1, 1 000 000]$에 속한다.

문제에서 설명한 수 S를 출력한다.

첫 번째 예제에서는 입력 수열을 두 부분 (3, 4), (7, 2)로 나눌 때 점수가 최대가 된다. 이때 총점은 이다.

두 번째 예제에서는 첫 번째 부분이 처음 세 원소로 이루어지고 두 번째 부분이 나머지 원소로 이루어질 때 점수가 최대가 된다. 이때 점수는 이다.