Гриби#5438
Маша вирішила провідати свою бабусю. Вона взяла з собою дві корзинки — одну з пиріжками, а другу — порожню, для грибів, які вона хоче зібрати по дорозі.
Для того, щоб потрапити до бабусі, Маші необхідно пройти через ліс, який являє собою прямокутник розміром m \times n, у деяких клітинках якого ростуть дерева, а у деяких — гриби. Маша виходить з клітинки і йде до бабусі у село, розміщене у клітинці . Кожним своїм ходом Маша може піти праворуч або вниз (тобто збільшує одну і лише одну зі своїх координат на ), якщо у клітинці, у якій вона після цього опиниться, не стоїть дерево. Якщо в обох клітинках — і праворуч, і внизу — знаходяться дерева, то вважається, що Маша заблукала.
Вам необхідно за заданим лісом з'ясувати, чи може Маша дійти до бабусі, не заблукавши, і, якщо зможе, то порахувати максимальну кількість грибів, які вона зможе при цьому зібрати.
У першому рядку вхідного файлу знаходяться чотири числа m, n, g, t (2 \leq m, n \leq 100, 0 \leq g, t \leq g + t \leq m n - 2). У наступних рядках розміщено по два числа у кожному — та -координати -го гриба. За ними йде рядків з описами дерев у аналогічному форматі. Ні у якій клітинці не може рости більше одного гриба, гриб та дерево одночасно, чи більше одного дерева. Крім того, у клітинках та нічого не росте.
Якщо Маша може дійти до бабусі, то у першому рядку вихідного файлу необхідно вивести максимальну кількість грибів, які вона зможе при цьому зібрати, а у наступних m + n - 1 рядках потрібно видати координати клітинок, послідовно відвіданих Машею у форматі x_i y_i, для шляху, на якому досягається максимальна кількість грибів. Якщо таких шляхів декілька, необхідно вивести той, який спускається вниз.
У протилежному випадку у вихідний файл повинно бути виведено єдине число .
Приклад 1
Приклад 2