В школе Фреда Хакера обучают \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 Для каждого теста вывести в отдельной строке одно целое число - минимально возможная энергия расписания, удовлетворяющего ограничениям.