**Обратите внимание: время на тест для этой задачи 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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
10 4 4
9 5 3
2 1 6
3 1
2 3
2 1
3 2
2 2
1 3
3 3
1 1
1 2
|
11
18
22
22
22
-1
-1
-1
-1
|