**Обратите внимание: время на тест для этой задачи 3сек, на 50% больше чем по умолчанию.
**
Ферма Джона может быть представлена как ориентированный взвешенный граф, с дорогами
(дугами), соединяющими различные вершины и вес каждой дуги есть время, которое требуется
чтобы проехать по этой дороге. Каждый день Беси любит путешествовать из амбара
(вершина \(1\)) в поле (вершина \(N\)), используя ровно \(K\) дорог и хочет добраться до поля
как можно быстрее при этих ограничениях. Однако, в некоторой точке, прекращается поддержка дорог
и они начинают ломаться одна за другой, становясь непроходимыми. Помогите Беси
определить кратчайший путь от амбара до поля во все моменты времени.
Формально, мы начинаем с полного взвешенного ориентированного графа из \(N\) вершин (\(1\le N\le 300\))
и \(N^2\) дуг: одна дуга для каждой пары \((i, j)\) \(1 \le i, j \le N\), заметим, что имеется
\(N\) петель (дуг из \(i\) в \(i\)). После каждого удаления выведите минимальный вес из всех путей
из \(1\) в \(N\), проходящих ровно \(K\) (необязательно различных) дуг \(2\le K\le 8\)).
Заметим, что после \(i\)-го удаленя в графе остаётся \(N^2-i\) дуг.
Вес пути определяется как сумма весов всех дуг в пути. Заметим, что путь может содержать
множество вхождений одних и тех же дуг, и одних и тех же вершин, включая \(1\) и \(N\).
ФОРМАТ ВВОДА (с клаватуры / stdin):
Первая строка содержит
\(N\) и
\(K\).
Следющие \(N\) строк содержат по \(N\) целых чисел каждая. \(j\)-ое целое \(i\)-ой строки
есть \(w_{ij}\) (\(1\le w_{ij}\le 10^8\)).
Затем следуют \(N^2\) дополнительных строк, каждая содержит два целых числа \(i\) и \(j\)
(\(1\le i,j\le N\)). Каждая пара целых чисел появляется ровно один раз.
ФОРМАТ ВЫВОДА (на экран / stdout):
Ровно \(N^2\) строк, минимальный вес \(K\)-пути после каждого удаления. Если \(K\)-путь не
существует, выведите \(-1\).
Ваш ответ: