Розклад уроків#2645
У школі Фреда Хакера є C \times T класів, розділених на категорій по класів у кожній. День починається з одночасного проведення всіх класів категорії . Після закінчення цих занять одночасно починаються всі заняття категорії , і так далі. Фред повинен вибрати рівно по одному заняттю з кожної категорії. Його мета — вибрати набір занять, що мінімізує загальну кількість "енергії", потрібної для проходження його щоденного розкладу.
Енергія розкладу — це сума енергії, потрібної для вибраних занять, і енергії, витраченої на переміщення від одного класу до наступного згідно з розкладом.
Вибір -го класу в -й категорії вимагає e_{ij} одиниць енергії. Класні кімнати розташовані на цілих позиціях уздовж коридору (нумерація від до ). -й клас у -й категорії знаходиться на позиції p_{ij}. Фред починає з позиції , відвідує вибрані кімнати у порядку категорій і закінчує у позиції . Переміщення на відстань коштує одиниць енергії.
Перший рядок містить (z \leq 20) — кількість тестів. Кожен тест починається з трьох цілих чисел , , (1 \leq c \leq 25, 1 \leq t \leq 1000, 1 \leq l \leq 1\,000\,000). Далі йдуть c \times t рядків, що описують класи: кожен клас задається розташуванням і енергоспоживанням. Перші рядків стосуються категорії , наступні — категорії і т.д. Гарантовано, що в межах однієї категорії жодні два класи не мають однакової позиції. Також 1 \leq e_{ij} \leq 1\,000\,000 та 0 \leq p_{ij} \leq l.
Пояснення до прикладу вводу
Фред повинен відвідувати заняття на день, і має варіанти на кожне. Довжина коридору — одиниць. Перше можливе заняття знаходиться в аудиторії і вимагає одиницю енергії на день і так далі.
Для кожного тесту в окремому рядку виведіть одне ціле число — мінімально можливу енергію для розкладу, що задовольняє вимогам.
Приклад 1