Tanya 现在五岁了,所以她所有的朋友都聚集在一起庆祝她的生日。有 n 个孩子参加庆祝活动,其中包括 Tanya。
庆典已接近尾声,最后计划的景点是游戏机。大厅里有 m 台机器,编号为 1 到 m。每个孩子都有一份他想玩的机器清单。此外,对于每台机器,他都知道他想要在上面玩的确切时间。对于每台机器,最多只能有一个孩子同时在这台机器上玩。
已经是晚上了,每个大人都想回家。为了加快这一过程,您还可以租用每台机器的第二个副本。要租用第 j 台机器的第二个副本,您必须支付 pj burles。租用机器后,您可以无限期地使用它。
如果您有 b burles 的预算用于租用额外的机器,需要多长时间才能让每个孩子按照自己的计划玩耍?每台机器只有一份,因此不可能租用第三台相同类型的机器。
孩子们可以随时中断游戏并稍后继续。如果第 i 个孩子想在第 j 台机器上玩,则在您租用第 j 台机器的副本后,允许该孩子一部分时间在第 j 台机器上玩,一部分时间在其副本上玩(这些部分都可以是空的)。中断和改变不需要时间并且可以在任何整数时刻执行。当然,一个孩子不能同时在多于一台机器上玩。
请记住,不需要省钱(没有人会以牺牲孩子的幸福为代价来省钱!),而是需要最小化某个孩子结束游戏的最新时刻。
输入
第一行包含三个整数 n、m 和 b (1 ≤ n ≤ 40, 1 ≤ m ≤ 10, 0 ≤ b ≤ 106) — 儿童数量、游戏机数量以及租用额外机器的预算。
第二行包含 m 个整数 p1, p2, ..., pm (1 ≤ pj ≤ 106),其中 pj 是第 j 台机器的第二个副本的租金价格。
接下来有 n 行,其中第 i 行描述了第 i 个孩子的愿望。该行以整数 ki (0 ≤ ki ≤ m) 开头——第 i 个孩子想要玩的机器数量。那么该行中有ki对,其中第y对是xiy,tiy。这意味着,第 i 个孩子想要在第 xiy (1 ≤ xiy ≤ m) 台机器上玩 tiy (1 ≤ tiy ≤ 2500) 分钟。在这 n 行的每一行中,值 xiy 都是不同的。
输出
在第一行中打印所有孩子完成游戏的最短时间。
在第二行中打印一个由零和一组成的长度为 m 的字符串。如果第 j 个机器的副本应该被评级,则第 j 个字符为“1”,否则为“0”。
第三行打印整数g(0≤g≤106)——所有孩子连续玩耍的时间段总数。然后在 g 行中将段打印为四个整数 i、j、s、d,这意味着第 i 个孩子从时间点 s (s ≥ 0) 开始在第 j 台机器或其副本上玩了 d 分钟 (d ≥ 1)。您可以按任意顺序打印这些行。
如果有多个答案,请打印其中任何一个。
示例
输入 #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