Грибы
Маша решила навестить свою бабушку. Она взяла с собой две корзинки - одну с пирожками, а другую - пустую, для грибов, которые она хочет собрать по пути.
Для того, чтобы попасть к бабушке, Маше необходимо пройти через лес, который представляет собой прямоугольник размером 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.