28264번 - Abode-Booked 서브태스크스페셜 저지

문제

선생님 정원이는 2023년 수학여행 행사를 계획하고 있다. 정원이는 지난 휴가 때 근사한 시간을 보낸 솔라 아일랜드에 가기로 계획하였다. 정원이의 학교에는 $B$개의 반이 있고, 각 반에는 학생 $P$명이 있어서 학생의 수는 총 $B \times P$명이다.

정원이는 학생들을 모두 수용할 수 있는 리조트를 찾다가 판도라 리조트를 발견하였다. 판도라 리조트는 $N$개의 건물이 일렬로 배치되어 왼쪽에서부터 $i+1$(0ドル \leq i < N$)번째 건물에는 번호 $i$가 붙어있다. $i$번 건물은 학생 $C_i$명을 수용할 수 있다. 인접한 두 건물 사이 거리는 모두 1ドル$로 동일하다.

정원이는 버스 $B$대를 확보하여 각 버스에 같은 반 학생 $P$명을 태워서 리조트로 이동하려고 한다. 각 버스는 건물이 있는 위치에 주차할 수 있으며 같은 건물에 여러 버스를 주차할 수 있다.

학생들은 버스에서 내린 후 자신이 머무를 리조트로 이동한다. 학생들의 이동 거리가 너무 길면 학생들을 통제하는 데 노력이 많이 들기 때문에 정원이는 학생 $B \times P$명의 총 이동 거리가 최소화되도록 리조트에 학생들을 배치하고 버스를 주차하려고 한다. 정원이를 도와 학생들의 배치와 버스를 주차하는 위치를 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에 리조트의 건물 수 $N,ドル 버스의 수 $B,ドル 버스당 인원수 $P$가 주어진다.

두 번째 줄에는 리조트의 각 건물당 수용할 수 있는 인원수 $C_i$에 해당하는 $N$개의 정수가 주어진다.

출력

첫 번째 줄에 정원이가 적절하게 버스와 학생들을 배치했을 때 학생들의 이동 거리의 합을 출력한다.

두 번째 줄부터 $B$개의 줄에는 $P+1$개의 정수를 출력하는데, 각 버스의 위치 $X_i$ (0ドル \leq X_i < N$)와 해당 버스에 타는 $P$명의 학생들이 사용할 리조트의 건물 번호 $S_{ij}$ (0ドル \leq S_{ij} < N$)를 출력한다.

가능한 정답이 여러 개라면 그중 아무거나 출력한다.

제한

서브태스크

힌트