eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Грибы

Грибы

Лимит времени 2 секунды
Лимит использования памяти 256 MiB

Маша решила навестить свою бабушку. Она взяла с собой две корзинки - одну с пирожками, а другую - пустую, для грибов, которые она хочет собрать по пути.

Для того, чтобы попасть к бабушке, Маше необходимо пройти через лес, который представляет собой прямоугольник размером m×n, в некоторых клетках которого растут деревья, а в некоторых - грибы. Маша выходит из клетки (1, 1) и идет к бабушке в деревню, расположенную в клетке (m, n). Каждым своим ходом Маша может пойти вправо или вниз (т.е. увеличить одну и только одну из своих координат на 1), если в клетке, в которой она после этого окажется, не стоит дерево. Если в обеих клетках и справа, и снизу, находятся деревья, то Маша считается заблудившейся.

Вам необходимо по данному лесу выяснить, может ли Маша дойти до бабушки, не заблудившись, и если может, то посчитать максимальное количество грибов, которое она может при этом собрать.

Входные данные

В первой строке входного файла находятся четыре числа m, n, g, t (2 ≤ m, n≤100, 0≤g, t≤g+t≤mn-2). В следующих g строках расположены по 2 числа в каждой - x и y-координаты i-го гриба. За ними следуют t строк с описаниями деревьев в аналогичном формате. Ни в какой клетке не может расти больше одного гриба, гриб и дерево одновременно, или больше одного дерева. Кроме того, в клетках (1, 1) и (m, n) ничего не растет.

Выходные данные

Если Маша может дойти до бабушки, то в первой строке выходного файла необходимо выдать максимальное количество грибов, которое она сможет при этом собрать, а в последующих m+n-1 строках нужно выдать координаты клеток, последовательно посещаемых Машей в формате x[i]y[i], для пути, на котором достигается максимальное количество грибов. Если таких путей несколько, то необходимо выдавать тот, который спускается вниз.

В противном случае в выходной файл должно быть выведено единственное число -1.

Пример

Входные данные #1
4 4 3 2
1 4
2 3
4 3
2 2
3 4
Выходные данные #1
2
1 1
1 2
1 3
2 3
3 3
4 3
4 4
Входные данные #2
2 2 0 2
1 2
2 1
Выходные данные #2
-1