E. Тане - 5 лет!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Тане исполнилось 5 лет и все её друзья собрались на праздновании дня рождения. Всего, включая Таню, на празднике присутствуют n детишек.

Праздник уже подходит к концу, но напоследок запланированы игровые автоматы. В зале, где проходит праздник, есть m игровых автоматов, которые пронумерованы от 1 до m. Каждый из детей уже составил список тех автоматов, в которые он хочет поиграть. Более того, если ребенок хочет поиграть на каком-то автомате, то он знает точно, сколько ему надо времени, чтобы насладиться игрой на нём. На любом автомате единовременно может играть только один ребенок.

Так как праздник уже затянулся, то все взрослые гости уже хотят по домам. Чтобы ускорить процесс вы можете дополнительно заказывать вторые экземпляры автоматов, для того чтобы арендовать второй экземпляр автомата j надо заплатить pj бурлей. Арендовав автомат, его можно использовать до конца праздника.

Как скоро все дети смогут поиграть в соответствии со своими пожеланиями, если у вас есть бюджет b бурлей на аренду дополнительных автоматов. Для каждого автомата в наличии есть только один запасной, так что арендовать третий экземпляр автомата нельзя.

Дети могут прерываться во время игры произвольным образом. Если 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-й ребенок хочет поиграть tiy (1 ≤ tiy ≤ 2500) минут на автомате xiy (1 ≤ xiy ≤ m). Для каждой из этих n строк среди значений xiy нет одинаковых.

Выходные данные

В первую строку выведите искомое минимальное время.

Во вторую строку выведите строку из нулей и единиц длины m, j-й символ равен '1', если был арендован дубликат j-го автомата.

В третью строку выведите g (0 ≤ g ≤ 106) — количество промежутков непрерывной игры всех детей. Далее в g строках выведите сами промежутки в виде четверки чисел i, j, s, d, которая обозначает, что ребенок i без перерыва играл в автомат j с момента времени s (s ≥ 0) в течение d (d ≥ 1) минут. Строки можно выводить в любом порядке.

Если ответов несколько, выведите любой из них.

Примеры
Входные данные
2 2 100
3 7
2 1 3 2 1
2 1 3 2 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
Входные данные
3 2 15
11 7
2 2 10 1 5
1 2 20
2 1 4 2 3
Выходные данные
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