놀이공원
시간 제한1초메모리 제한512 MB
각 기계의 이용 시간이 정해진 놀이공원에서 N명이 M개의 기계를 모두 한 번씩 이용하도록 순서와 시작 시각을 정해, 가장 이른 버스 출발 시각과 각 참가자의 일정을 출력한다.
문제
도시 π에 놀이공원이 새로 문을 열었고, 그 안에는 게임기 파빌리온이 있다. 각 게임기는 한 사람만 사용할 수 있다. 전러시아 올림피아드 참가자들은 이 파빌리온을 방문할 예정이다.
주최자에게는 어려운 과제가 하나 주어졌다. N명의 참가자 각자가 모든 게임기를 한 번씩 해 보고, 참가자들을 놀이공원에서 숙소로 데려다줄 버스가 최대한 이른 시각에 출발할 수 있도록 게임기 사용 일정을 짜는 것이다.
참가자가 게임기 사이를 이동하는 시간과 버스와 파빌리온 사이를 이동하는 시간은 0으로 본다. 각 참가자는 어느 순간에든 게임기를 하거나, 공원을 거닐며 자기 차례를 기다릴 수 있다. M개의 게임기(M ≤ N) 각각에 대해 게임 시간 ti(1 ≤ i ≤ M)가 주어진다. 시작한 게임을 중간에 멈출 수는 없다. 버스는 모든 참가자를 0시각에 놀이공원에 동시에 내려 준다.
N, M, ti가 주어졌을 때 각 참가자의 게임기 사용 일정을 최적으로 정하는 프로그램을 작성해야 한다.
입력
첫째 줄에 두 정수 N과 M이 주어진다(1 ≤ M ≤ N ≤ 100). 둘째 줄에 M개의 정수 ti가 주어지며, 각각 i번째 게임기의 게임 시간을 나타낸다(1 ≤ i ≤ M). 줄 안의 수는 하나의 공백으로 구분된다.
출력
첫째 줄에 버스가 놀이공원을 떠날 수 있는 가장 이른 시각을 나타내는 정수 하나를 출력한다. 이어서 각 참가자의 게임 일정을 N개 출력하는데, 참가자마다 하나씩이다. 각 일정은 (M + 1)개의 줄로 이루어지며, 첫 줄은 빈 줄이고, 그다음 M개의 줄에는 그 참가자가 방문하는 게임기를 방문 순서대로 적는다. 게임기 방문은 두 정수, 즉 게임기 번호 j(1 ≤ j ≤ M)와 그 게임기에서 참가자의 게임 시작 시각으로 나타낸다.
제한
ti는 1 이상 100 이하이고, N > M이다.