CF737E 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)$。你可以以任意顺序输出这些行。 如果有多个可能的答案，请输出其中任意一个。