G. Песочные часы
ограничение по времени на тест
0.5 секунд
ограничение по памяти на тест
24 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Для измерения времени в Средние века мастеровые использовали песочные часы. Так как такие часы были достаточно редки и дороги, то не у каждого мастера был набор часов, позволяющих отмерить любой интервал времени. Мастера были людьми изобретательными и умудрялись с помощью минимума часов производить очень сложные измерения. Например, с помощью часов на 3 и 5 минут можно отмерить любое количество минут, большее четырех. А сможете ли Вы превзойти наших предков?

У вас есть $$$n$$$ (до 4) песочных часов, пронумерованных числами $$$1$$$, $$$2$$$, ..., $$$n$$$, песок в которых пересыпается за $$$t_1$$$, $$$t_2$$$, ..., $$$t_n$$$ (до 20) минут соответственно. Напишите программу, которая найдет способ отмерить с помощью этих часов $$$k$$$ минут. Учтите, что:

  • любые часы можно переворачивать только в самом начале измерений, либо в момент, когда в каких-то часах закончился песок
  • в такой момент можно перевернуть одновременно любое количество часов — переворачивание часов происходит мгновенно
  • часы запрещено класть набок (останавливать время)
  • измеряемый интервал в $$$k$$$ минут начинается с самого первого переворачивания любых часов
  • измеряемый интервал в $$$k$$$ минут должен заканчиваться в момент, когда в каких-нибудь часах закончился песок.

Например, пусть у нас есть песочные часы на 3 и 5 минут. Покажем, как с их помощью можно отмерить 7 минут:

  • 0 минут. Одновременно переворачиваем часы и на 3 и на 5 минут.
  • 3 минуты. Часы на 3 минуты пусты, а в часах на 5 минут есть песок еще на 2 минуты. Переворачиваем часы на 3 минуты.
  • 5 минут. Часы на 5 минут пусты, в часах на 3 минуты есть песок еще на 1 минуту сверху, и на 2 минуты снизу. Переворачиваем часы на 3 минуты.
  • 7 минут. Часы на 3 минуты пусты. Заданный интервал отмерен.
Входные данные

Первая строка входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 4$$$) — количество песочных часов. Вторая строка содержит целые числа $$$t_1$$$, $$$t_2$$$, ..., $$$t_n$$$ ($$$1 \leq t_1 \lt t_2 \lt \ldots \lt t_n \leq 20$$$), разделенные пробелами — номиналы песочных часов. Третья строка содержит целое число $$$k$$$ ($$$1 \leq k \leq 1440$$$) — интервал времени, который нужно отмерить.

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

Первая строка выходных данных содержит $$$-1$$$, если интервал времени $$$k$$$ отмерить нельзя. В противном случае, она содержит целое число $$$r$$$ — количество моментов времени ($$$1 \leq r \leq k$$$), в которые осуществляется переворачивание часов. Далее следуют $$$r$$$ строк, описывающих моменты переворачивания часов.

Каждая такая строка начинается с числа $$$t_i$$$ — числа минут от начала отсчета времени до момента данного переворачивания. Далее, через пробел следует число $$$m_i$$$ ($$$0 \leq m_i \leq n$$$) — число часов переворачиваемых в момент времени $$$t_i$$$. Далее, через пробел указываются номера переворачиваемых часов.

Строки должны выводиться в порядке увеличения момента времени: $$$t_i \gt t_{i-1}$$$. В момент времени $$$t_i$$$ должен заканчиваться песок в хотя бы в одних часах.

Первая строка должна содержать описание начального момента времени ($$$t_1=0$$$). Последняя строка должна содержать момент времени $$$k$$$ и 0 переворачиваемых часов. Строки с временем $$$t_i \gt k$$$ появляться не должны, строки с $$$m_i = 0$$$ допускаются и не считаются ошибкой.

Примеры
Входные данные
2
3 5
7
Выходные данные
4
0 2 1 2
3 1 1
5 1 1
7 0
Входные данные
2
3 5
4
Выходные данные
-1
Входные данные
2
7 9
13
Выходные данные
5
0 2 1 2
7 1 1
9 2 1 2
11 1 2
13 0