Розклад уроків
У школі Фреда Хакера викладають 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 одиницю енергії щодня, і так далі.
Вихідні дані
Для кожного тесту виведіть в окремому рядку одне ціле число - мінімально можлива енергія розкладу, що задовольняє обмеженням.