Rainbow Sheep (4/8 Points)

Rainbow Sheep

Baa, baa, bright sheep,

Have you any wool?

Yes, sir, yes, sir,

n bags full;

Some coloured crazy,

and others rather lame,

But there's a single rule

That I must explain

Collect all the wool,

And colours you'll weigh.

The top take the bottom

should leave at most K.

You are a special lab made sheep called "Dolly" which grows rainbow wool. The local farmers and craftspeople in the town would like various colours of wool for their use, but because you grow all colours of wool at equal speeds, you can't give too much more of one colour than another.

In particular, every person would like exactly 1 "unit" of wool, and will only accept certain colours. For a particular colour $c$, let $a_c$ be the units of wool of that colour given to people. You must have it so that $\max_c(a_c) - \min_c(a_c) \leq k$ for some constant $k$. In other words, you cannot give $k+1$ more units of wool of one colour than some other colour.

For a particular selection of colours, what is the maximum number of people we can give wool to while still obeying the rules of colour distribution, and for this maximum number of people, what is the largest value of $\min_c(a_c)$?

Input

Input will begin with three space separate integers, $n$, $k$ and $c$. These are:

• The number of people that want wool $n$
• The constant $k$
• The number of colours $c$

$n$ lines will follow, detailing the colour preferences of each of the people.

Each line will begin with a single integer $c_i$, the number of colours this person accepts, and then the line will contain an additional $c_i$ space-separated integers, represent the colours that the $i$th person accepts.

Output

Output should begin with a single integer $p$, the maximum number of people the sheep can give a unit of wool to. Output should next contain $p$ lines, each containing two integers:

• The 1-index of the person to give wool
• The colour of the wool to give that person

This method of giving wool to each person should also maximise the minimum amount of any colour wool given out (Subject to the maximum total wool constraint already being followed).

Constraints

• $1 \leq n \leq 400$
• $1 \leq c \leq 100$
• The total number of preferences will not exceed $600$

Test Set A (50% of the points)

• $k = 0$ (So many aspects of the problem can be ignored!)

Test Set B (50% of the points)

• $1 \leq k \leq 100$

Example 1

For input

6 1 3
1 1
2 1 2
3 1 2 3
2 1 2
1 1
1 1

A possible solution is

5
1 1
2 2
3 3
4 2
5 1

This way, the maximum number of units assigned per colour (2 people, achieved by colours 1 and 2), and the minimum number of units assigned per colour (1 person, achieved by colour 3), differ by at most $k$.

Example 2

For input

6 6 3
1 1
2 1 2
3 1 2 3
2 1 2
1 1
1 1

A possible solution would not be:

5
1 1
2 1
3 1
4 1
5 1

While this is maximal in terms of wool given out, and does follow the rules of the problem, the value of $\min(a_c)$ (The minimum amount of a particular colour of wool is given) is $0$. The solution to Example 1 shows we can give the same amount of wool out while having $\min(a_c) = 1 > 0$.