Overview

This is just a subproblem that I have learned before. However, I don't have the testcases or the place to submit this.

Describe

Give 2 * n colors with the their frequency (Each of them have to appear at least once). Sum of all their frequency is m * n. Make a table with size m * n (m rows, n column) that minimize the max numbers of different color in each column (And the frequency of color is same above) ?

Input

The first line of input contains two integers m and n (m, n <  = 50). The second line contains 2 * n integers — the frequency of each color. The sum values of them equal exactly m * n.

4 4
1 1 2 2 2 4 1 3

Output

Output the table that satisfied the statement above.

1 7 4 6
2 3 4 6
6 3 5 8
6 8 5 8

Explain

• Color 1 has to appear 1 times;
• Color 2 has to appear 1 times;
• Color 3 has to appear 2 times;
• Color 4 has to appear 2 times;
• Color 5 has to appear 2 times;
• Color 6 has to appear 4 times;
• Color 7 has to appear 1 times;
• Color 7 has to appear 3 times;

Sum of them is: 1 + 1 + 2 + 2 + 2 + 4 + 1 + 3 = 16 = m * n.

• Column 1 has 3 different colors.
• Column 2 has 3 different colors.
• Column 3 has 2 different colors.
• Column 4 has 2 different colors.

So the maximum different colors in each column is 3, which is the best answer in this case.

My approach

My teacher said that the answer is only equal 2 or 3.

• In case the answer is 2, we just sort the frequency of colors and merge the most frequency and the least frequency color together in the first column, do the same thing with (n - 1) other column.
• However, when the answer is 3, he just said the the greedy approach could do this.

I have tried some greedy approach, like merge this first least and the second least frequency color (we can prove that sum of them always  <  = m) with the most frequency color. But I already found a conner case for this.

I have ask many people (include my teacher — who always said is just a easy greedy problem -_-) but I couldn't found a correct approach. So now I post this, thank you Codeforces community.

UPD 1: Add the application to automatic draw the rectangle.

Overview

This problem is a varient of the classic problem, "Packing rectangles with the smallest area rectangle.". This is also an optimization with you may not find the most optimal solution but the more rectangles you can place, the more score you get.

In this problem, given the size of the main rectangle and the size of others rectangles, find the maximum number of rectangle could be place in the main rectangle without overlapping the other rectangle ( note: these rectangles must be inside the main rectangle — but it can be touch in the borders of the main rectangle).

Input

The first line contains three integers n, m and k (1 ≤ n, m ≤ 100, 1 ≤ k ≤ 1000) — the height, the width of the fixed rectangle and the number of rectangles to be placed.

The next k lines have two integers x_i and y_i (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m) — the height and the width of the rectangle, remember that we can't rotate these rectangles.

Output

The first line of the ouput print k.

The next k line print two number x_j and y_j is the top — left point where the rectangle j placed. In case we don't place this rectangle, print "0 0" (without quotes).

Sample input

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

Sample output

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

Illustration

Picture for sample test case

Illustration application

Using the application

To use the application, you run your code to make a new ".exe" file (it must be in same folder with the input test). After that, upload the test input by clicking the button "Load input file...". Finally, click the button "Run external solution ..." and chose your ".exe" file.

P/s: Hope you to help with problem in case we want to maximize the area be covered. I just think of the brute force solution and some of the trival greedy approachs.

As you see, my new rating is 1608, however, it dislay as 1689 (old rating before the Codeforces Round 226 (Div. 2)). The rating changes in the contest and the graph have show may exactly my new rating — except the dislay in my home page — sorry I don't know how to call it.

I have to see some other user and I have the same bug, I just see their new color but still old rating.

Also, when I open the Problemset Status with friend only, I just see the submission before the contest, although after the contest I have make a submission in 745B - Hongcow Solves A Puzzle — and it change to green in the Problemset but I can't see the submisson in the Status.

So I ask my friend but he couldn't find anybug. I think maybe the problem is about my account, so I log out and see the rating again, but the bug still there :(.

Anyone please help me with this problem. Thank you you guy a lots.