Problem - 775A - Codeforces

VK Cup 2017 - Wild Card Round 2
Finished

→ Problem tags

*special problem

*2900

No tag edit access

In this problem your task is to come up with a week schedule of classes in university for professors and student groups. Consider that there are 6 educational days in week and maximum number of classes per educational day is 7 (classes numerated from 1 to 7 for each educational day).

It is known that in university n students study, m professors work and there are a classrooms for conducting classes. Also you have two-dimensional array with n × m size which contains the following information. The number which stays in i-th row and j-th column equals to the number of classes which professor j must conduct with the group i in a single week. The schedule which you output must satisfy to array described above.

There are several other conditions for schedule. Single professor can not conduct more than one class. Similarly, single student group can not be on more than one class at the same time.

Let define a fatigue function for professors and student groups. Call this function f.

To single professor fatigue calculated in the following way. Let look on classes which this professor must conduct in each of the 6-th educational days. Let x be the number of class which professor will firstly conduct in day i and let y — the last class for this professor. Then the value (2 + y - x + 1)·(2 + y - x + 1) must be added to professor's fatigue. If professor has no classes in day i, nothing is added to professor's fatigue.

For single student group fatigue is calculated similarly. Lets look at classes of this group in each of the 6 educational days. Let x be the number of first class for this group on day i and let y — the last class for this group. Then the value (2 + y - x + 1)·(2 + y - x + 1) must be added to this group's fatigue. If student group has no classes in day i, nothing is added to group's fatigue.

So the value of function f equals to total {fatigue} for all n student groups and for all m professors.

Your task is to come up with such a schedule which minimizes the value of function f.

Jury prepared some solution of this problem. For each test you will get a certain number of points. It equals to result of division of the value of function f from the jury solution by the value of function f for schedule which your program output (i. e. the smaller value of {fatigue} function your program find the more points you will get), multiplied by 100. In the other words if the value of f for jury solution equals to p and for your solution — to q, you will get 100·p / q points (note, that the number of points is a real number). The points will be added together for all tests. The goal is to score as many points as possible.

Input

The first line contains three integers n, m and a (1 ≤ n, m, a ≤ 60) — the number of groups, the number of professors and the number of classrooms.

Each of the following n lines contains m integers from 0 to 24 — j-th number in i-th line equals to the number of classes with the professor j must conduct with the i-th student group.

It is guaranteed that the number of classes in week for each professor and for each student group does not exceed 24. Also guaranteed that the total number of classes in week does not exceed 75% from a maximum number of classes which can be conducted based on the number of classrooms. For all tests there is at least one schedule satisfying all described conditions.

Output

In the first line print the minimized value of function f.

After that print blank line.

After that print the schedule for each student group in increasing order of group number. For each student group print 7 lines. Each line must contains 6 numbers. Let the number at i-th line and j-th column equals to x. If in j-th day current group has no class number i, x must be equals to zero. Otherwise x must be equals to the number of professor who will conduct the corresponding class with the corresponding student group.

The number of classes which will be conducted simultaneously must not exceeds the number of classrooms a.

Separate the description of the schedules for groups with a blank line.

Examples

Input

Output

54

1 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 

0 0 0 0 0 0 
2 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 

0 0 0 0 0 0 
0 0 0 0 0 0 
3 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0

Input

Output

52

1 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 

0 0 0 0 0 0 
1 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 

0 0 0 0 0 0 
0 0 0 0 0 0 
1 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0

Input

5 7 10
1 3 6 0 1 2 4
0 3 0 6 5 1 4
3 5 1 2 3 2 4
2 3 1 1 4 1 2
2 4 3 2 4 3 2

Output

1512

0 0 6 0 0 2 
0 7 6 3 3 7 
3 1 2 3 2 7 
3 7 0 0 0 0 
5 3 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 

0 0 4 0 7 6 
4 5 7 4 5 5 
7 2 4 4 5 5 
7 2 0 4 0 0 
0 2 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 

4 0 7 2 5 7 
5 0 2 5 7 1 
2 4 1 2 7 1 
2 3 0 0 0 0 
0 6 0 0 0 0 
0 6 0 0 0 0 
0 0 0 0 0 0 

0 0 0 5 3 5 
0 2 4 7 2 6 
0 5 7 0 0 0 
1 5 1 0 0 0 
2 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 

0 0 5 7 2 3 
0 1 3 2 6 3 
5 7 6 5 6 4 
5 4 2 2 0 0 
1 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0

Note

During the main part of the competition (one week) you solution will be judged on 100 preliminary tests. The first 10 preliminary tests are available for download by a link http://assets.codeforces.com/files/vk/vkcup-2017-wr2-materials-v1.tar.gz.

After the end of the contest (i.e., a week after its start) the last solution you sent (having positive score) will be chosen to be launched on the extended final tests.