30098번 - 스쿨 아이돌 프로젝트 GSHS 스페셜 저지

문제

누구나 시선을 빼앗기는 너는 완벽한 궁극의 아이돌

아이돌 애니메이션을 인상 깊게 시청한 종경이는 경기과학고등학교에서도 아이돌 그룹을 만들 계획을 세웠다. 이에 따라 정보과학세미나2를 수강하는 학생들 $N$명을 불러 모아 몇 개의 아이돌 그룹을 결성하고자 한다.

$N$명의 학생이 일렬로 서 있고, $i$번째 학생의 매력은 $a_i$로 표현된다. $(1 \le i \le N)$ 종경이는 이 학생들을 몇 개의 아이돌 그룹으로 분할하려고 한다. 하나의 아이돌 그룹은 연속한 학생들로 구성되어야 하며, 각 학생은 정확히 하나의 아이돌 그룹에 속해야 한다. 또, 너무 많은 학생이 한 그룹에 속하지 않도록 하나의 아이돌 그룹은 $M$명 이하의 학생으로 구성되어야 한다. 한 아이돌 그룹의 매력은 그 아이돌 그룹에 속한 학생의 매력 중 최댓값에서 최솟값을 뺀 값과 같다.

종경이는 학생들을 적절히 분할하여 아이돌 그룹을 구성하여 모든 아이돌 그룹의 매력의 합이 최대가 되는, 완벽한 궁극의 아이돌을 만들려 한다. 여러분이 종경이를 도와주자.

입력

첫째 줄에 $N,ドル $M$이 공백을 사이에 두고 주어진다.

둘째 줄에 $N$명 학생의 매력 $a_1, \cdots, a_N$이 공백을 사이에 두고 주어진다.

출력

첫째 줄에 모든 아이돌 그룹의 매력의 합의 최댓값을 출력한다.

둘째 줄부터 $(K+2)$번째 줄까지 매력의 합이 최댓값이 되는 예시를 다음과 같은 형식으로 출력한다.

둘째 줄에는 그룹 개수 $K$를 출력한다.

셋째 줄부터 $(K+2)$번째 줄까지 $(i+2)$번째 줄에는 그룹 구성 방법을 나타내는 두 정수 $l_i,ドル $r_i$를 공백을 사이에 두고 출력한다. $(1 \le i \le K)$ 이는 $i$번째의 그룹이 $l_i$번째 학생부터 $r_i$번째 학생까지로 구성됨을 의미한다.

매력의 합이 최대가 되는 아이돌 그룹 구성 방법이 여러 가지 있다면, 이 중 어떤 것을 출력해도 좋다.

제한

입력 제한

• 1ドル \le N \le 300,000円$
• 1ドル \le M \le N$
• 1ドル \le a_i \le 10^9$ $(1 \le i \le N)$
• 입력으로 주어지는 모든 수는 정수이다.

출력 제한

• 1ドル \le K \le N$
• $l_1=1$
• $r_K=N$
• $r_i+1=l_{i+1}$ $(1 \le i < K)$
• 1ドル \le r_i-l_i+1 \le M$ $(1 \le i \le K)$

힌트