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

Есеп E. Дене шынықтыру

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

2 секунд

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

256 мегабайт

Оқушылар арасында пәндер бойынша өтетін олимпиадалардың тізіміне дене шынықтыруды қосу шешілді, жекелей айтқанда, спорттық жүру, кедергісіз жүгіру, кедергімен жүгіру, қаптармен жүгіру және тағы басқалар. Оргкомитет спорттың әр түріне бір маршрутты дайындауы тиіс. Жарысты ұйымдастыру үшін шаршыларға бөлінген $N \times M$ болатын тіктөртбұрышты территория бөлінді. Әр шаршы үшін оның жарыстарға дайындау бағасы анықталды. Оған қоса, қатысушылардың маршруты бастала және аяқтала алатын шаршылар белгілі. Маршрут деп әр екі көрші шаршының ортақ қабырғасы бар шаршылар тізбегін атайық. Жарыстардың барлық түрі бір уақытта болатындықтан ешқандай екі маршрут қиылыспауы тиіс, егер олар қиылысса, онда қатысушылар бір-біріне кедергі жасайды. Сіздің мақсатыңыз — оргкомитетке маршруттарды дайындау бағаларының қосындысы минимал болатындай етіп таңдауға көмектесу.

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

Енгізу файлының бірінші жолында үш сан берілген: $N$, $M$ және $K$ ($1 \le N, M, K \le 30$), онда $N$, $M$ — территоряның өлшемі, а $K$ — жарыстар түрлерінің саны. Келесі $N$ жолдың әрқайсысы $1$-ден $100$-ге дейінгі $M$ бүтін саннан — сәйкесінше шаршының жарысқа дайындау бағасы тұрады. Келесі $K$ жолдың әрқайсысы $2$ бүтін саннан — кездейсоқ маршрут бастала алатын шаршының жолы мен қатарының нөмірлері. Соңғы $K$ жолдың әрқайсысы $2$ бүтін саннан — кездейсоқ маршрут аяқтала алатын шаршының жолы мен қатарының нөмірлері. Енгізу файлында ешқандай шаршы екі рет жазылмаған. Жолдағы сандар бос жолмен бөлінген.

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

Егер берілген шартарға қанағаттандыратын маршрут болмаса, шығыс файлда ``$No solution$'' жолын шығару керек. Кері жағдайда бірінші жолда дайындау бағасы ең азын, ал келесі жолдарда маршруттар картасын шығар. Маршурттар картасы — $N \times M$ таблица. $i$-шы жолдың $j$-ші қатарында $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$ кепілдік беріледі.