Расписание уроков
В школе Фреда Хакера обучают t × c предметам, разделенных на c категорий, каждая из которых содержит t предметов. День начинается занятиями из категории 1, которые проводятся одновременно. Все они заканчиваются в одно и то же время. Потом начинаются занятия категории 2 и так далее. Фред должен прослушать в точности один предмет из каждой категории. Ему необходимо выбрать предметы таким образом, чтобы минимизировать количество энергии, необходимой для выполнения ежедневного расписания.
Энергия распсания равна сумме энергий предметов в нем плюс энергия перехода из одного класса в другой согласно расписанию.
Изучение j-го предмета из i-ой категории требует e_ij единиц энергии. Классные комнаты, где преподаются предметы, находятся в целочисленных точках (пронумерованных от 0 до l) вдоль одного коридора. Класс, в котором преподается j-ый предмет i-ой категории расположен в позиции p_ij. Фред начинает свой день в позиции 0, переходит из класса в класс соответственно выбранному расписанию, и завершает свой путь в позиции l. Передвижение на расстояние d требует потребления d единиц энергии.
Входные данные
Первая строка содержит количество тестов z (z ≤ 20). Каждый тест начинается тремя целыми числами c, t и l (1 ≤ c ≤ 25, 1 ≤ t ≤ 1000, 1 ≤ l ≤ 1,000,000). Каждая из следующих c×t строк описывает соответственно местоположение и потребление энергии в классе. Первые t строк описывают предметы категории 1, следующие t строк описывают предметы категории 2 и так далее. Никакие классные комнаты не имеют одинакового положения. Известно, что 1 ≤ e_ij ≤ 1,000,000 и 0 ≤ p_{ij }≤ l.
Пояснение к тесту
Фред должен изучать каждый день по 3 предмета, и каждый день у него имеется по 2 выбора. Длина коридора равна 5. Первый предмет Фреда проходит в классе в позиции 2 и требует 1 единицу энергии каждый день, и так далее.
Выходные данные
Для каждого теста вывести в отдельной строке одно целое число - минимально возможная энергия расписания, удовлетворяющего ограничениям.