Дивани

Обмеження: 2 сек., 256 МіБ

Зеник і Марічка роблять ремонт у вітальні.

Марічка приготувала план розміщення усіх меблів, окрім дивану. Це завдання вона доручила Зенику, який дуже любить дивани, і хоче розмістити їх якомога більше.

Кімната має квадратний розмір і складається із \(n \times n\) одиничних квадратів. План розташування меблів можна зобразити у вигляді матриці \(A\) із \(n\) рядків та \(n\) стовпців, де значення \(A_{ij}\) рівне 1, якщо відповідний одиничний квадрат вже заповнений меблями, або 0 якщо ні.

Зеник хоче розмістити якомога більше диванів розміру \(1 \times (n-1)\) або \((n-1) \times 1\). Ваше завдання — допомогти йому знайти цю найбільшу кількість.

Зауважте, що дивани не можуть перетинатись; їх слід розташовувати паралельно до стін не займаючи вже зайнятий простір; границі диванів повинні збігатися із границями одиничних квадратів.

Вхідні дані

У першому рядку задано одне ціле число \(n\) — розмір стін.

У наступних \(n\) рядках задано по \(n\) символів 0 або 1 в кожному, без пробілів — матриця \(A\). Символ 1 означає, що відповідний квадрат зайнятий, 0 — вільний.

Вихідні дані

У єдиному рядку виведіть одне ціле число — максимальну кількість диванів.

Обмеження

\(3 \le n \le 50\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 111 000 000	3

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 000 100 101	3

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 0000 0000 0000 0000	5

Примітки

У першому прикладі оптимально розмістити три дивани наступним чином (однакові букви позначають позиції дивану):

У другому прикладі також можна розмістити три дивани:

У третьому прикладі можна розмістити 5 диванів: