2022 Fall Waterloo Local Contest, Problem D

The University of Wonderfulness has accidentally admitted more students than it has the capacity to teach. Unfortunately, this means that some of its courses may be full and some students might not be able to take the courses that they would like. Can you help the university manage the situation?

Each student has selected ~5~ courses that they would like to take. Each course has a hard limit on the number of students that can take it. Your task is to enroll each student into as many of their ~5~ selected courses as possible while respecting the course limits.

The happiness level of a student is the number of courses that they are enrolled in. If they can enroll in all ~5~ of their selected courses, their happiness level is ~5~. If two of their selected courses are full and they can enroll in only ~3~ of their ~5~ selected courses, their happiness level is only ~3~. The university wishes to maximize the sum of the happiness levels of all the students.

The objective can be phrased in a different but equivalent way. Each student pays ~\$1\,000~ in tuition for each course that they are enrolled in. A student with all ~5~ of their selected courses pays ~\$5\,000~. A student enrolled in only ~3~ of their ~5~ selected courses pays ~\$3\,000~. The university wishes to maximize the total amount of tuition it can collect.

Your task is to assign students to courses while respecting the constraints and maximizing the total happiness level of the students and the total amount of tuition collected.

Input Specification

The first line of input contains two integers separated by a space, ~5 \le c \le 1\,000~, the number of courses, and ~1 \le s \le 10\,000~, the number of students. It is followed by ~c~ lines, the ~i^\text{th}~ such line containing a single integer ~1 \le m_i \le 10\,000~, the maximum number of students that can be enrolled in the ~i^\text{th}~ course. These ~c~ lines are followed by ~s~ more lines, one for each student. Each of these ~s~ lines contains five distinct integers separated by spaces, the five courses that the student would like to take. Each of these course numbers is an integer ~1 \le i \le c~, corresponding to the course whose limit ~m_i~ was given on the ~i^\text{th}~ of the ~c~ lines following the first line of input.

Output Specification

The first line of output should contain a single integer, the maximum sum of the happiness levels that can be achieved. This first line of output should be followed by ~s~ more lines, one for each student, in the same order as in the input. Each of these lines should contain between ~0~ and ~5~ integers separated by spaces, the course numbers ~1 \le i \le c~ of the courses that the student is enrolled in to achieve the maximum sum of happiness levels on the first line of output.

If there are multiple assignments of courses to students that achieve the same maximum sum of happiness levels, you may output any one of those assignments and it will be considered correct.

Sample Input

6 3
1
1
1
1
1
1
1 2 3 4 5
1 2 3 4 5
1 2 3 4 6

Sample Output

6
1 2 3 4 5

6

Note

The original problem did not have a sample.