Увімкнення світла#11157
Фермер Джон нещодавно побудував величезний сарай, що складається із сітки кімнат розміром n \times n, пронумерованих від до . Оскільки корова Бессі трохи боїться темряви, вона хоче увімкнути світло у якомога більшій кількості кімнат.
Бессі починає в кімнаті , яка є єдиною кімнатою, де спочатку увімкнено світло. У деяких кімнатах вона знайде вимикачі, за допомогою яких зможе вмикати світло в інших кімнатах. Наприклад, у кімнаті може знаходитися вимикач, який вмикає світло в кімнаті . Бессі може переміщатися лише по кімнатах, у яких увімкнено світло, і з кімнати вона може перейти лише в одну з чотирьох сусідніх кімнат: (x - 1, y), (x + 1, y), (x, y - 1) або (x, y + 1) (або в меншу кількість сусідніх кімнат, якщо кімната знаходиться на межі сітки).
Визначте максимальну кількість кімнат, у яких Бессі зможе увімкнути світло.
У першому рядку містяться два цілих числа і m~(2 \le n \le 100, 1 \le m \le 20000).
Кожен із наступних рядків описує один вимикач і містить чотири цілих числа x, y, a та . Вимикач, розташований у кімнаті , можна використати, щоб увімкнути світло в кімнаті . В одній кімнаті може знаходитися декілька вимикачів, а декілька вимикачів можуть вмикати світло в одній і тій самій кімнаті.
Виведіть одне ціле число — максимальну кількість кімнат, у яких Бессі зможе увімкнути світло.
У цьому прикладі Бессі може використати вимикач у кімнаті , щоб увімкнути світло в кімнатах і . Потім вона може пройти в кімнату і увімкнути світло в кімнаті , з якої зможе увімкнути світло в кімнаті . Вимикач у кімнаті недоступний, оскільки він знаходиться в кімнаті з вимкненим світлом. Тому Бессі зможе увімкнути світло максимум у кімнатах.
Приклад 1