Tanya is 5!

题意翻译

## 题目描述 Tanya 五岁了！所以她所有的朋友都来给她庆祝生日。包括Tanya在内，一共有 $n$ 个孩子参加了庆典。 庆典就快要结束了，还有最后一项活动——玩游戏机没有完成。在大厅里放着 $m$ 台游戏机，它们的编号为 $1\!\sim\!m$ 。 每个孩子都有一个游戏机清单，上面有他想玩的游戏机编号和对应的时间。对于每一台游戏机，在同一时刻只能被一个孩子使用。 现在已经是傍晚了，大人们都想快点回家。为了加快这个活动的进程，对于每一台机器你都可以额外租用**一台**备用机器。对于编号为 $j$ 的机器的备用机，租金为 $p_j$ 。当你租用了一台备用机以后，它可以在任何时间被使用。备用机和游戏机一样，在同一时刻只能被一个孩子使用。 如果你有 $b$ 元预算来租用备用机，需要多长时间才能使所有孩子都完成他们的游戏机清单？每台游戏机只有一台备用机可租用，所以你不可能拥有三台编号相同的机器。 孩子们可以在任意时间停止或者继续游戏。在你租用了第 $j$ 台游戏机的备用机后，如果第 $i$ 个孩子想要玩第 $j$ 台游戏机，他可以花一部分时间玩第 $j$ 台游戏机，花另一部分时间玩第 $j$ 台游戏机的备用机（每一部分都可以为空）。停止和改变使用机器的行为都可以在任何整数时刻发生，并且认为是瞬间完成，不花费时间。当然，一个孩子不可能同时使用两台机器。 记住，这不是为了省钱（没有人会为了省钱而牺牲孩子的快乐！）, 这是为了尽量缩短孩子们完成清单所需的时间。 ## 输入格式 第一行包含三个整数 $n$，$m$ 和 $b$ $(1\!\le\!n\!\le\!40 $，$1\!\le\!m\!\le\!10$，$0\!\le\!b\!\le\!10^6)$，分别表示孩子数量，游戏机数量和预算。 第二行包含 $m$ 个整数 $p_1$，$p_2$，$\dots$，$p_m(1\!\le\!p_j\!\le\!10^6)$，其中 $p_j$ 表示编号为 $j$ 的游戏机的备用机所需租金。 接下来有 $n$ 行，第 $i$ 行描述了第 $i$ 个孩子的游戏机清单。每一行开头有一个整数 $k_i(0\!\le\!k_i\!\le\!m)$ ，表示第 $i$ 个孩子想玩的游戏机的数量。之后有 $k_i$ 对数，第 $y$ 对是 $x_{iy},t_{iy}$ 。这表示第 $i$ 个孩子想在编号为 $x_{iy}$ 的游戏机上玩 $t_{iy}$ 分钟。在这 $n$ 行中，$x_{iy}$ 的值是不同的。$(1\!\le\!x_{iy}\!\le\!m$，$1\!\le\!t_{iy}\!\le\!2500)$ ## 输出格式 在第一行输出所有孩子完成他们的游戏机清单的最小时间。 在第二行输出一个长度为 $m$ 的$01$字符串，如果租用了编号为 $j$ 的游戏机的备用机，那么第 $j$ 个字符为 $1$，否则为 $0$。 在第三行输出一个整数 $g(0\le\!g\!\le10^6)$，表示所有孩子连续玩游戏机的时间片段总数。 接下来 $g$ 行输出四个整数 $i$，$j$，$s$，$d$，表示第 $i$ 个孩子从 $s$ $(0\le\!s)$ 时刻开始玩了 $d\;(1\le\!d)$。你可以以任意顺序输出这些行。 如果有多个可能的答案，请输出其中任意一个。

题目描述

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 $ p_{j} $ 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.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ and $ b $ ( $ 1<=n<=40 $ , $ 1<=m<=10 $ , $ 0<=b<=10^{6} $ ) — the number of children, the number of gaming machines and the budget for renting additional machines. The second line contains $ m $ integers $ p_{1},p_{2},...,p_{m} $ ( $ 1<=p_{j}<=10^{6} $ ), where $ p_{j} $ 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 $ k_{i} $ ( $ 0<=k_{i}<=m $ ) — the number of machines, the $ i $ -th child wants to play on. Then there are $ k_{i} $ pairs in the line, the $ y $ -th of them is $ x_{iy} $ , $ t_{iy} $ . It means that, the $ i $ -th child wants to play $ t_{iy} $ ( $ 1<=t_{iy}<=2500 $ ) minutes on the $ x_{iy} $ -th ( $ 1<=x_{iy}<=m $ ) machine. In each of these $ n $ lines the values $ x_{iy} $ are distinct.

输出格式

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<=10^{6} $ ) — 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.

输入输出样例

输入样例 #1

2 2 100
3 7
2 1 3 2 1
2 1 3 2 1

输出样例 #1

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

输入样例 #2

3 2 15
11 7
2 2 10 1 5
1 2 20
2 1 4 2 3

输出样例 #2

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