English · Original
Chinese · Translation
Formal · Original
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.
## Input
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 _p_1, _p_2, ..., _p__m_ (1 ≤ _p__j_ ≤ 106), 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.
## Output
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.
[samples]
Tanya 现在五岁了，她的所有朋友都聚在一起为她庆祝生日。庆祝活动中共有 #cf_span[n] 个孩子，包括 Tanya。
庆祝活动即将结束，最后一个安排的项目是游戏机。大厅里有 #cf_span[m] 台机器，编号为 #cf_span[1] 到 #cf_span[m]。每个孩子都有一个他想玩的机器列表，并且对于每台机器，他知道他想玩的确切时间。对于每台机器，同一时间最多只能有一个孩子使用。
现在已经到了晚上，每位家长都想回家。为了加快进程，你可以额外租用每台机器的第二份副本。租用第 #cf_span[j] 台机器的第二份副本需要支付 #cf_span[pj] 布勒。租用后，你可以无限期使用该副本。
如果你有 #cf_span[b] 布勒的预算用于租用额外机器，那么让每个孩子按照计划玩完游戏需要多长时间？每种机器只有一份原始机器，因此无法租用第三台同类型机器。
孩子们可以在任意时刻中断游戏，并在之后继续。如果第 #cf_span[i] 个孩子想在第 #cf_span[j] 台机器上玩，那么在你租用了第 #cf_span[j] 台机器的副本后，该孩子可以在原始机器和副本上分别玩一部分时间（这两部分时间可以为空）。中断和切换无需时间，可以在任意整数时刻进行。当然，一个孩子不能同时在多台机器上玩。
请注意，不需要省钱（没有人会为了省钱而牺牲孩子的快乐），你需要最小化最后一个孩子结束游戏的时刻。
第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[b] (#cf_span[1 ≤ n ≤ 40], #cf_span[1 ≤ m ≤ 10], #cf_span[0 ≤ b ≤ 106]) —— 孩子数量、游戏机数量和租用额外机器的预算。
第二行包含 #cf_span[m] 个整数 #cf_span[p1, p2, ..., pm] (#cf_span[1 ≤ pj ≤ 106])，其中 #cf_span[pj] 是租用第 #cf_span[j] 台机器第二份副本的价格。
接下来 #cf_span[n] 行，第 #cf_span[i] 行描述第 #cf_span[i] 个孩子的愿望。该行以一个整数 #cf_span[ki] (#cf_span[0 ≤ ki ≤ m]) 开头，表示第 #cf_span[i] 个孩子想玩的机器数量。接着有 #cf_span[ki] 对数，第 #cf_span[y] 对是 #cf_span[xiy], #cf_span[tiy]，表示第 #cf_span[i] 个孩子想在第 #cf_span[xiy] 台机器（#cf_span[1 ≤ xiy ≤ m]）上玩 #cf_span[tiy]（#cf_span[1 ≤ tiy ≤ 2500]）分钟。在每行中，#cf_span[xiy] 的值互不相同。
第一行输出所有孩子完成游戏所需的最短时间。
第二行输出一个长度为 #cf_span[m] 的由 0 和 1 组成的字符串。第 #cf_span[j] 个字符为 '_1_' 表示应租用第 #cf_span[j] 台机器的副本，为 '_0_' 表示不租用。
第三行输出一个整数 #cf_span[g] (#cf_span[0 ≤ g ≤ 106]) —— 所有孩子连续游戏时间段的总数。然后在 #cf_span[g] 行中，每行输出四个整数 #cf_span[i], #cf_span[j], #cf_span[s], #cf_span[d]，表示第 #cf_span[i] 个孩子在第 #cf_span[j] 台机器或其副本上，从时刻 #cf_span[s]（#cf_span[s ≥ 0]）开始持续玩了 #cf_span[d] 分钟（#cf_span[d ≥ 1]）。你可以按任意顺序输出这些行。
如果有多个答案，输出任意一个即可。
## Input
第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[b] (#cf_span[1 ≤ n ≤ 40], #cf_span[1 ≤ m ≤ 10], #cf_span[0 ≤ b ≤ 106]) —— 孩子数量、游戏机数量和租用额外机器的预算。第二行包含 #cf_span[m] 个整数 #cf_span[p1, p2, ..., pm] (#cf_span[1 ≤ pj ≤ 106])，其中 #cf_span[pj] 是租用第 #cf_span[j] 台机器第二份副本的价格。#cf_span[n] 行接续，第 #cf_span[i] 行描述第 #cf_span[i] 个孩子的愿望。该行以一个整数 #cf_span[ki] (#cf_span[0 ≤ ki ≤ m]) 开头，表示第 #cf_span[i] 个孩子想玩的机器数量。接着有 #cf_span[ki] 对数，第 #cf_span[y] 对是 #cf_span[xiy], #cf_span[tiy]，表示第 #cf_span[i] 个孩子想在第 #cf_span[xiy] 台机器（#cf_span[1 ≤ xiy ≤ m]）上玩 #cf_span[tiy]（#cf_span[1 ≤ tiy ≤ 2500]）分钟。在每行中，#cf_span[xiy] 的值互不相同。
## Output
第一行输出所有孩子完成游戏所需的最短时间。第二行输出一个长度为 #cf_span[m] 的由 0 和 1 组成的字符串。第 #cf_span[j] 个字符为 '_1_' 表示应租用第 #cf_span[j] 台机器的副本，为 '_0_' 表示不租用。第三行输出一个整数 #cf_span[g] (#cf_span[0 ≤ g ≤ 106]) —— 所有孩子连续游戏时间段的总数。然后在 #cf_span[g] 行中，每行输出四个整数 #cf_span[i], #cf_span[j], #cf_span[s], #cf_span[d]，表示第 #cf_span[i] 个孩子在第 #cf_span[j] 台机器或其副本上，从时刻 #cf_span[s]（#cf_span[s ≥ 0]）开始持续玩了 #cf_span[d] 分钟（#cf_span[d ≥ 1]）。你可以按任意顺序输出这些行。如果有多个答案，输出任意一个即可。
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of children, $ m \in \mathbb{Z}^+ $ the number of machines, $ b \in \mathbb{Z}_{\geq 0} $ the budget.
Let $ \mathbf{p} = (p_1, \dots, p_m) \in \mathbb{Z}_{\geq 1}^m $ be the cost vector for renting a second copy of each machine.
Let $ \mathcal{C} = \{1, \dots, n\} $ be the set of children.
For each child $ i \in \mathcal{C} $, let $ W_i \subseteq \{1, \dots, m\} \times \mathbb{Z}^+ $ be the set of requested play intervals: $ (j, t) \in W_i $ means child $ i $ wants to play $ t $ minutes on machine $ j $.
Let $ x_j \in \{0,1\} $ indicate whether a second copy of machine $ j $ is rented ($ x_j = 1 $) or not ($ x_j = 0 $).
Let $ \mathcal{M}_j = \{ j \} $ if $ x_j = 0 $, or $ \{ j, j' \} $ if $ x_j = 1 $, where $ j' $ denotes the rented copy.
**Constraints**
1. $ 1 \leq n \leq 40 $, $ 1 \leq m \leq 10 $, $ 0 \leq b \leq 10^6 $
2. $ 1 \leq p_j \leq 10^6 $ for all $ j \in \{1, \dots, m\} $
3. For each child $ i $, $ 0 \leq |W_i| \leq m $, and for all $ (j,t) \in W_i $, $ 1 \leq t \leq 2500 $
4. Total rental cost: $ \sum_{j=1}^m x_j p_j \leq b $
5. For each machine $ j $, at most one child can use any single physical instance (original or copy) at any time.
6. A child’s total play time on machine $ j $ must equal $ \sum_{(j,t) \in W_i} t $, possibly split between the original and its copy (if rented).
7. Play segments are non-overlapping in time for each machine instance.
**Objective**
Minimize the makespan $ T = \max_{i \in \mathcal{C}} \{ \text{end time of child } i \} $, subject to the above constraints.
API Response (JSON)
{
"problem": {
"name": "E. Tanya is 5!",
"description": {
"content": "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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF737E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Tanya is now five so all her friends gathered together to celebrate her birthday. There are _n_ children on the celebration, including Tanya.\n\nThe celebration is close to its end, and the last planned...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Tanya 现在五岁了，她的所有朋友都聚在一起为她庆祝生日。庆祝活动中共有 #cf_span[n] 个孩子，包括 Tanya。\n\n庆祝活动即将结束，最后一个安排的项目是游戏机。大厅里有 #cf_span[m] 台机器，编号为 #cf_span[1] 到 #cf_span[m]。每个孩子都有一个他想玩的机器列表，并且对于每台机器，他知道他想玩的确切时间。对于每台机器，同一时间最多只能有一个孩子使用。...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of children, $ m \\in \\mathbb{Z}^+ $ the number of machines, $ b \\in \\mathbb{Z}_{\\geq 0} $ the budget. \nLet $ \\mathbf{p} = (p_1, \\dots, p_m) ...",
"is_translate": false,
"language": "Formal"
}
]
}