Tanya is 5!
Contest: Codeforces Round 380 (Div. 1, Rated, Based on Technocup 2017 - Elimination Round 2)
Difficulty rating: 3300
Tags: graph matchings, graphs, greedy, schedules

Tanya is now five so all her friends gathered together to celebrate her birthday. There are n children on the celebration, including Tanya.

The celebration is close to its end, and the last planned attraction is gaming machines. There are m machines in the hall, they are numbered 1 through m. Each of the children has a list of machines he wants to play on. Moreover, for each of the machines he knows the exact time he wants to play on it. For every machine, no more than one child can play on this machine at the same time.

It is evening already, so every adult wants to go home. To speed up the process, you can additionally rent second copies of each of the machines. To rent the second copy of the j-th machine, you have to pay pj burles. After you rent a machine, you can use it for as long as you want.

How long it will take to make every child play according to his plan, if you have a budget of b burles for renting additional machines? There is only one copy of each machine, so it's impossible to rent a third machine of the same type.

The children can interrupt the game in any moment and continue it later. If the i-th child wants to play on the j-th machine, it is allowed after you rent the copy of the j-th machine that this child would play some part of the time on the j-th machine and some part of the time on its copy (each of these parts could be empty). The interruptions and changes take no time and can be performed in any integer moment of time. Of course, a child can't play on more than one machine at the same time.

Remember, that it is not needed to save money (no one saves money at the expense of children happiness!), it is needed to minimize the latest moment of time some child ends his game.

Input format:
The first line contains three integers n, m and b (1 ≤ n ≤ 40, 1 ≤ m ≤ 10, 0 ≤ b ≤ 106) — the number of children, the number of gaming machines and the budget for renting additional machines.

The second line contains m integers p1, p2, ..., pm (1 ≤ pj ≤ 106), where pj is the rent price for the second copy of the j-th machine.

n lines follow, i-th of them describes the wishes of the i-th child. The line starts with an integer ki (0 ≤ ki ≤ m) — the number of machines, the i-th child wants to play on. Then there are ki pairs in the line, the y-th of them is xiy, tiy. It means that, the i-th child wants to play tiy (1 ≤ tiy ≤ 2500) minutes on the xiy-th (1 ≤ xiy ≤ m) machine. In each of these n lines the values xiy are distinct.

Output format:
In the first line print the minimum time in which all the children can finish their games.

In the second line print a string of length m consisting of zeros and ones. The j-th character is '1', if the copy of j-th machine should be rated, and '0' otherwise.

In the third line print integer g (0 ≤ g ≤ 106) — the total number of time segments of continuous playing for all of the children. Then in g lines print the segments as four integers i, j, s, d, meaning that the i-th child was playing on the j-th machine or its copy from the time moment s (s ≥ 0) for d minutes (d ≥ 1). You can print these lines in arbitrary order.

If there are multiple answers, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2 2 100
3 7
2 1 3 2 1
2 1 3 2 1

Example output:
4
10
8
1 1 0 1
2 2 0 1
1 1 1 1
2 1 1 1
2 1 2 1
1 1 2 1
1 2 3 1
2 1 3 1

Example input:
3 2 15
11 7
2 2 10 1 5
1 2 20
2 1 4 2 3

Example output:
20
01
17
2 2 0 4
2 2 4 1
1 1 5 2
2 2 5 2
1 2 7 5
2 2 7 5
2 2 12 1
1 2 12 1
3 1 13 4
2 2 13 4
1 2 13 4
1 1 17 2
3 2 17 2
2 2 17 2
1 1 19 1
2 2 19 1
3 2 19 1

Editorial:
The problem was invented by the recollections of the recent celebration of the fifth birthday of Tanya Mirzayanova.
At first let's solve this problem in simplified form: let there is no duplicate machines (in the other word it does not enough the budget b to rent any duplicate).
We consider, that each kid would like to play in each machine. Let ti, j = 0 in such case. So, we consider, that the values of t is a rectangular table — for each pair kid/machine in the cell written down the time of the game.
Note that minimal time when all games will ended does not less than sum of values in each row Ri = ti, 1 + ti, 2 + ... + ti, m. Similarly, the minimal time when all games will ended does not less than the sum in each column Cj = t1, j + t2, j + ... + tn, j, because on each machine in one moment of time can play no more than one kid.
Because of that the minimal time does not less than max(R1, R2, ..., Rn, C1, C2, ..., Cm). Note that there is always such a schedule that needed minimal time equals to maximum of all rows sums and all columns sums. Let's call this value T.
Now we need to show this fact and consider the way to get this schedule.
Let's build the weighted bipartite graph. In each part of this graph is n + m vertices.
Let's assume that each machine has a fake kid (i. e. now we have n + m kids) — n real and m fake kids. The vertices from the first part will for kids: u1, u2, ..., un — for real kids and un + 1, un + 2, ..., un + m — for fake kids, and un + j is a fake kid for the machine j.
Similarly, let consider that each kid has a fake machine (totally there will be n machines). The vertices from the second part will for machines: the first m vertices is for real machines (v1, v2, ..., vm), and following n for fakt machines (vm + 1, vm + 2, ..., vm + n). The vertex vm + i will for the fake machine of kid i.
Let's make the edges. We will have 4 types of edges:
1. between the real kids and the real machines,
2. between the fake kids and the real machines,
3. between the real kids and the fake machines,
4. between the fake kids and the fake machines.
We need to make the edges in such a way that the sum of weights of incident edges for each vertex is equals to T.
The edges of type 1. Let's add the edge between ui and vj, if ti, j > 0. the weight is ti, j. This edge means that the kid must play on the machine needed number of minutes.
The edges of type 2. This edges mean that the machine will has downtime equals to some number of minutes (in the other words in downtime the fake kid will play on this machine). For all j from 1 to m let's find a - Cj. If such vertices is positive, then we need to add edge between un + j и vj with such weight.
The edges of type 3. This edges mean that the kid will have time, when he does not play (we consider that in this time the kid play on the fake machine). For all i from 1 to n let's find a - Ri. If this value is positive we add edge between ui and vm + i with such weight.
The edges of type 4. After we added the edges of types 1-3 it is easy to show that the sum of weights of incident edges equal to T. For the vertices un + 1, un + 2, ..., un + m, vm + 1, vm + 2, ..., vm + n this sum now less or equal to T. Let's add remaining edges to make this sums equal to T. It's always possible if we add this edges in greedy way.
We know the following fact: in any regular bipartite graph there is a perfect matching (a consequence of the Hall's theorem).
If we look on the given graph like on the unweighted multigraph where the weight of the edge in our graph equals to the number of edges between the pair of vertices, then the resulting graph will be regular graph and for it will be correct described fact (i. e. there is perfect matching in this graph).
Let's find the perfect matching with help of the Kuhn's algorithm in weighted graph. Let's choose the weight of the minimal edge and it is equals to M. Then let's appoint kids on machines for each edge between the vertices u1, u2, ..., un и v1, v2, ..., vm on the time M. Also let's subtract M from the weight of each edge of the matching. If the weight of the edge became 0, we delete this edge.
After that it is correct the sum for each vertices is a constant. It means that the remaining graph has the perfect matching. We need to make with this graph similar operations, which was described above.
Let's do it until the graph contains at least one edge. So we found needed schedule.
To make the solution faster we can rebuild the matching from the unsaturated vertices from the first part if such vertices exist. This algorithm will works totally in O(e2), where e is the number of edges in the beginning, i. e. e = O(nm), so the asymptotic behavior is O(n2m2). In this problem there were small restricts so we could build the matching with Kuhn's algorithm.
By the way we build the optimal painting of the bipartite graph. Here we can use the well known algorithm (read about the optimal painting of the bipartite graph).
So, we solved the problem without rent the duplicates. Besides it, the value of the answer is a maximum from all sums of rows and columns of the table with times for pairs kid/machine.
If we have a duplicated it equals to adding the column in which we can partially distribute the values from this column. Of course, it is profitably to make it with columns which sum Cj = T (i. e. the answer rests in this column). This operation makes sense only if we make it for all columns with Cj = T simultaneously.
The algorithm to choose of machines to rent follows. Let's find the sum of rent for all machines with Cj = T. If this value less or equal to the budget b than we must rent this machines. Then add the appropriate columns in the table and put as evenly as possible the values of the duplicated columns. Recalculate T. Repeat the process and end it when the sum of rent for each operation became more than b.