Республиканская олимпиада по информатике 2009 год

Задача E. Физкультура

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

В список предметных олимпиад школьников решили, наконец, внести и физкультуру, в частности, спортивную ходьбу, бег без препятствий, бег с препятствиями, бег в мешках и так далее. Оргкомитет должен подготовить по одному маршруту для каждого вида соревнований. Для проведения соревнований была выделена прямоугольная территория, которую для удобства разделили на квадраты так, что получилась сетка $N \times M$. Для каждого квадрата была определена стоимость его подготовки к соревнованиям. Также были определены квадраты, в которых могут начинаться и оканчиваться маршруты участников. Маршрутом будем считать такую последовательность квадратов, что каждые два соседних квадрата в этой последовательности имеют общую сторону. Так как все виды соревнований будут проводиться параллельно, никакие два маршрута не должны пересекаться по квадратам, иначе участники будут мешать друг другу. Ваша задача — помочь оргкомитету выбрать маршруты так, чтобы суммарная стоимость подготовки их к соревнованиям была минимально возможной.

Формат входного файла

Первая строка входного файла содержит три целых числа: $N$, $M$ и $K$ ($1 \le N, M, K \le 30$), где $N$, $M$ — размеры территории, а $K$ — количество видов соревнований. Каждая из следующих $N$ строк содержит по $M$ целых чисел в пределах от $1$ до $100$ — стоимость подготовки соответствующего квадрата к соревнованиям. Следующие $K$ строк содержат по $2$ целых числа — номер строки и столбца для квадрата, в котором может начинаться какой-нибудь маршрут. Последние $K$ строк содержат также по $2$ целых числа — номер строки и столбца для квадрата, в котором может заканчиваться какой-нибудь маршрут. Никакой квадрат не перечислен во входном файле дважды. Числа в строках разделены пробелами.

Формат выходного файла

В выходной файл нужно вывести ``$No solution$'', если невозможно выбрать $K$ маршрутов, удовлетворяющих условию. В противном случае на первой строке выведите наименьшую суммарную стоимость подготовки, а на следующих строках — карту маршрутов. Карта маршрутов — это таблица размера $N \times M$, в $j$-м столбце $i$-й строки которой расположен $0$, если через соответствующих квадрат не проходит ни один маршрут, и целое положительное число $X$ ($1 \le X \le K)$, если через него проходит маршрут для соревнования $X$. Если оптимальных ответов несколько, то выведите любой. Числа в строках разделяйте пробелом.

Пример:

Вход

3 3 2
1 1 1
1 1 1
10 1 1
1 1
1 3
3 2
3 3

Ответ

7
2 0 1
2 2 1
0 2 1

Гарантируется, что в некотором подмножестве тестов, суммарно не превышающем $50$ баллов, $K = 1$.