Задачі
Class Schedule
Class Schedule
В школе Фреда Хакера обучают \textbf{t }× \textbf{c }предметам, разделенных на \textbf{c }категорий, каждая из которых содержит \textbf{t }предметов. День начинается занятиями из категории \textbf{1}, которые проводятся одновременно. Все они заканчиваются в одно и то же время. Потом начинаются занятия категории \textbf{2} и так далее. Фред должен прослушать в точности один предмет из каждой категории. Ему необходимо выбрать предметы таким образом, чтобы минимизировать количество энергии, необходимой для выполнения ежедневного расписания.
Энергия распсания равна сумме энергий предметов в нем плюс энергия перехода из одного класса в другой согласно расписанию.
Изучение \textbf{j}-го предмета из \textbf{i}-ой категории требует \textbf{e_ij} единиц энергии. Классные комнаты, где преподаются предметы, находятся в целочисленных точках (пронумерованных от \textbf{0 }до \textbf{l}) вдоль одного коридора. Класс, в котором преподается \textbf{j}-ый предмет \textbf{i}-ой категории расположен в позиции \textbf{p_ij}. Фред начинает свой день в позиции \textbf{0}, переходит из класса в класс соответственно выбранному расписанию, и завершает свой путь в позиции \textbf{l}. Передвижение на расстояние \textbf{d} требует потребления \textbf{d} единиц энергии.
\InputFile
Первая строка содержит количество тестов \textbf{z }(\textbf{z }≤ \textbf{20}). Каждый тест начинается тремя целыми числами \textbf{c}, \textbf{t }и \textbf{l }(\textbf{1 }≤ \textbf{c }≤ \textbf{25}, \textbf{1 }≤ \textbf{t }≤ \textbf{1000}, \textbf{1 }≤ \textbf{l }≤ \textbf{1,000,000}). Каждая из следующих \textbf{c}×\textbf{t }строк описывает соответственно местоположение и потребление энергии в классе. Первые \textbf{t }строк описывают предметы категории \textbf{1}, следующие \textbf{t }строк описывают предметы категории \textbf{2} и так далее. Никакие классные комнаты не имеют одинакового положения. Известно, что \textbf{1 }≤\textbf{ e_ij }≤ \textbf{1,000,000 }и \textbf{0 }≤ \textbf{p_\{ij \}}≤ \textbf{l}.
\textit{\textbf{Пояснение к тесту}}
Фред должен изучать каждый день по \textbf{3} предмета, и каждый день у него имеется по \textbf{2} выбора. Длина коридора равна \textbf{5}. Первый предмет Фреда проходит в классе в позиции \textbf{2} и требует \textbf{1} единицу энергии каждый день, и так далее.
\OutputFile
Для каждого теста вывести в отдельной строке одно целое число - минимально возможная энергия расписания, удовлетворяющего ограничениям.
Вхідні дані #1
1 3 2 5 2 1 3 1 4 1 1 3 1 4 3 2
Вихідні дані #1
11
Пояснення: Here is one way to obtain the minimum energy: Go to the class at location 2. Energy used: 3 Next, go to the class at location 4. Energy used: 6 Then go to the class at location 3. Energy used: 9 Finally, leave the school at location 5. Energy used: 11