암호화 (어려움)

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 ≤ 500 000, 2 ≤ k ≤ 100, 2 ≤ p ≤ 100)이 주어진다. 이들은 각각 A의 원소 수, A를 나누어야 하는 부분의 수, 점수를 계산할 때 사용할 법이다.

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

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

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

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