암호화 (중간)

Heidi는 이제 Death Star 계획의 첫 번째 암호화 단계를 풀었고, 화면에 표시된 다음 입력 코드의 설명을 바라보고 있다. 놀랍게도 첫 번째 것과 매우 비슷해 보인다. Empire의 기술자들은 상당히 게으른 듯하다...

Heidi에게 다시 수열 A가 주어지지만, 이제 두 정수 k와 p도 주어진다. Heidi는 암호화 키 S가 무엇인지 알아내야 한다.

Let X을 정수 수열이라 하고, p를 양의 정수라 하자. X의 점수를 X의 원소 합을 p로 나눈 나머지로 정의한다.

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

• 각 부분은 A의 원소를 적어도 1개 포함하며, A에서 연속한 원소들로 이루어진다.
• No 두 부분이 겹친다.
• 이 부분들의 점수의 총합 S가 최대가 되어야 한다.

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

입력의 첫째 줄에는 공백으로 구분된 세 정수 N, k, p (k ≤ N ≤ 20 000, 2 ≤ k ≤ 50, 2 ≤ p ≤ 100)가 주어진다. 각각 A의 원소 수, A를 나누어야 하는 부분의 수, 점수를 계산할 때 사용할 모듈러스를 나타낸다.

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

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

첫 번째 예제에서 입력 수열을 (3, 4), (7), (2)로 나누면 총점은 가 된다. 이 점수가 최댓값임을 쉽게 알 수 있다.

두 번째 예제에서 점수 37을 얻을 수 있는 한 가지 방법은 다음과 같이 나누는 것이다: (16, 3, 24), (13, 9), (8), (7), (5, 12, 12).