창의적인 회계

시간 제한2초메모리 제한128 MB

요약

일별 잔액이 주어질 때, 연속한 구간의 합을 m으로 나눈 나머지가 최대가 되는 구간을 골라 그 나머지의 최댓값을 구한다.

난이도: 어려움10점 중 8점
유형: 누적 합, 수학, 정렬, 이분 탐색
정답자: 아직 제출이 없습니다

문제

바이트아사르(Byteasar)와 친구들은 유명한 휴양지 바이텐-바이텐에서 여름 휴가를 보내고 있다. 관광객이 많은 곳이라 물가가 비싸서, 이들은 틈틈이 일을 해 여행 경비를 보탰다. 바이트아사르는 모임 전체의 회계(총무)를 맡았다.

휴가가 끝나면 모임은 정산을 한다. 친구들은 전체 잉여금(또는 빚)을 모임 인원수 $m$ 명으로 똑같이 나누기로 했다. 만약 정확히 나누어떨어지지 않으면, 회계를 맡은 보상으로 바이트아사르가 공동 예산에서 남는 금액을 가져가 나머지 금액이 인원수로 나누어떨어지도록 한다. 총액이 빚(음수)일 때에도 그의 보상은 빚을 늘리는 방향으로 적용된다.

바이트아사르가 받는 보상은 선택한 기간의 총 수지 $S$ 를 $m$ 으로 나눈 나머지와 정확히 같다. 여기서 나머지는 항상 $0$ 이상 $m-1$ 이하의 값으로 정의한다. 다시 말해 $S - r$ 이 $m$ 의 배수가 되는 유일한 $r \in [0, m-1]$ 이 그의 보상이다. 예를 들어 $S = 30$ , $m = 13$ 이면 $30 = 2 \times 13 + 4$ 이므로 보상은 $4$ 이고, $S = -1$ , $m = 13$ 이면 $-1 = (-1) \times 13 + 12$ 이므로 보상은 $12$ 다.

바이트아사르는 얄팍한 계획을 세웠다. 그는 친구들에게 $l$ 번째 날부터 $r$ 번째 날까지에 해당하는 장부의 일부만 보여주기로 했다( $1 \le l \le r \le n$ ). 그는 이 연속된 기간의 총 수지에 대한 보상이 최대가 되도록 구간을 고르려 한다.

회계 보상이 최대가 되도록 기간을 최적으로 선택했을 때 바이트아사르가 받게 되는 금액을 구하는 프로그램을 작성하라.

입력

첫째 줄에 두 정수 $n$ 과 $m$ 이 주어진다( $1 \le n \le 200\,000$ , $2 \le m \le 10^{18}$ ). $n$ 은 휴가 일수, $m$ 은 바이트아사르를 포함한 모임의 인원수다. 둘째 줄에는 $n$ 개의 정수 $a_i$ 가 주어진다( $|a_i| \le 10^{18}$ ). $a_i$ 는 $i$ 번째 날의 수지(바이탈러 단위)이며, 양수는 수입이 지출보다 많음을 뜻한다.

출력

바이트아사르가 회계 보상으로 받을 수 있는 최대 금액(바이탈러)을 정수 하나로 출력한다.

예제3

예제 1
입력
```
5 13
10 9 5 -5 7
```
예상 출력
```
11
```
예제 2
입력
```
2 10
1 9
```
예상 출력
```
9
```
예제 3
입력
```
1 5
7
```
예상 출력
```
2
```