Рабочее место участника

В лабиринте размером `N\ times\ N` с одним выходом кладоискатель нашел клад и хочет вынести его из лабиринта за минимальное количество ходов. У него есть `r` единиц взрывчатки, которая позволяет уничтожить единичную часть внутренней (но не внешней!) стены лабиринта. Ход – это переход в соседнюю клетку по горизонтали или вертикали с возможным одновременным взрывом мешающей части стены. Верхняя левая клетка лабиринта имеет координаты (1,1).

Во входном файле в первой строке содержится целые числа `N` (`2\ ≤\ N\ ≤\ 50`) и `r` (`0\ ≤\ r\ ≤\ 3`), координаты кладоискателя `x,\ y` (`0\ <\ x,\ y\ ≤\ N`, `x` – столбец, `y` – строка) и координаты выхода `u,\ v` (`0\ ≤\ u,\ v\ ≤\ N+1`). Во второй строке указывается количество единичных частей внутренних стен `m` (`0\ ≤\ m\ ≤\ 2*(N-1)*N`). В последующих `m` строках находятся координаты клеток `a_i`, `b_i` и `c_i`, `d_i` (`0\ <\ a_i,b_i,c_i,d_i\ ≤\ N`), между которыми находится `i`-я единичная часть стены.

В выходной файл вывести минимальное количество ходов и количество использованной взрывчатки. Если есть несколько путей одинаковой длины, то выбрать путь с минимальным использованием взрывчатки. Если путь до выхода не найден, то вывести 0 0.

4 1 1 1 3 0
9
1 1 2 1
2 2 1 2
1 3 2 3
2 1 3 1
3 2 3 1
4 2 4 3
3 3 2 3
3 3 3 4
2 4 3 4

7 1