Директор сети магазинов бытовой техники «Родонит» подсчитывал убытки за месяц. Прошли те времена, когда покупатели забирали из магазина приобретённые ими товары сразу после покупки. Теперь они требуют бесплатную доставку, да чтобы ещё заранее позвонили с целью выяснить, в какое время им удобней привезти товар.

В городе работают 10 магазинов «Родонит». Как человек с высшим образованием, директор понял, что невыгодно доставлять товары прямо из тех магазинов, где они были приобретены. На окраине города (чтобы приходилось меньше платить за аренду помещения) находится склад бытовой техники, а рядом со складом гараж. Грузовик для доставки товаров у компании имеется всего один. Казалось бы, сломайся грузовик, и клиенты не смогут получить товар вовремя, но директор об этом не думал. Как вы уже поняли, он привык экономить на всём. Грузовик каждый день, развозя товары, расходует огромное количество бензина, что не может не огорчать директора, учитывая постоянный рост цен на топливо. Проблема в том, что грузовик не всегда может за один рейс развезти все товары со склада клиентам: грузоподъёмность его не так уж и велика. По ночам сотрудники компании составляют список товаров на складе, которые были куплены в прошедший день, и поэтому должны были быть доставлены на следующий. Для каждого товара указываются данные клиента, который приобрёл данный товар: фамилия, адрес, телефон. Далее специально обученными служащими составляется план развоза: в какой рейс какие товары должен забрать шофёр со склада, а также порядок объезда клиентов во время выполнения каждого из рейсов. По возможности такой план должен уменьшить расходуемое при развозе горючее.

Служащие, естественно, считают, что для минимизации истраченного горючего достаточно минимизировать пройденное грузовиком расстояние. Они измеряют по карте города попарные кратчайшие расстояния между объектами (объектами служащие называют склад и всех клиентов из списка). Далее начинается сложный оптимизационный процесс… При вычислениях делаются следующие допущения:

1. Расстояние между гаражом и складом = 0.
2. Пусть D(i, j) — кратчайшее расстояние между объектами i и j. Тогда для любых объектов i, j, k
   1. D(i, i) = 0.
   2. D(i, j) = D(j, i).
   3. D(i, k) ≤ D(i, j) + D(j, k).
3. В конце каждого рейса грузовик должен вернуться в гараж.
4. Грузовик может увезти в один рейс множество товаров, если суммарная масса всех товаров из этого множества не превосходит грузоподъёмности грузовика.

За работу по ночам служащим приходится платить сверхурочные. Поэтому экономный директор решил нанять на работу одного программиста. Программист должен написать программу, находящую по информации о товарах и клиентах план развоза по крайней мере не хуже, чем составленный служащими вручную. Если вы ещё не догадались, этот программист — вы.

В первой строке даны целые положительные числа M ≤ 20 — количество клиентов, N ≤ 50 — количество товаров и L_max ≤ 3000 — грузоподъёмность грузовика. В следующих строках записана матрица D размером (M+1)×(M+1) расстояний между объектами (склад имеет номер 0, клиенты — номера от 1 до M). Далее в N строках расположена информация о товарах: масса текущего товара и номер клиента-заказчика (целое число от 1 до M). Все массы и расстояния на вводе — целые числа в пределах [1,100].

В первой строке укажите число рейсов, которое нужно совершить. Далее должны следовать блоки информации о рейсах (одному рейсу соответствует один блок). Блок состоит из четырёх строк: в первой приведены через пробел номера доставляемых за данный рейс товаров в любом порядке (номера лежат в пределах от 1 до N), во второй — загрузка грузовика (суммарная масса доставляемых товаров), в третьей — маршрут (номера объектов через пробел в порядке объезда), в четвёртой — пройденное расстояние за рейс. В последней строке выведите суммарное пройденное расстояние за все рейсы. Разделяйте числа в строке ровно одним пробелом, блоки отделяйте друг от друга, а также от первой и последней строк пустыми строками, как показано в примере.

Считается, что ваша программа успешно проходит тест, если она выдаёт ответ не хуже, чем выдаёт программа жюри на том же наборе входных данных.