Трава для Кози-дерези

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

Багато часу пройшло від усім відомих подій за участю Кози-дерези. Налякана Коза пробігла без зупинки сім кілометрів, аж раптом зрозуміла, що зголодніла.

Коза вирішила зупинитись неподалік від поля розміром \(n \times n\), розбитого на одиничні клітинки. Клітинка з координатами \((1, 1)\) є лівою верхньою клітинкою поля. Кожна клітинка або повна поживної та свіжої трави, або залита бетоном. Для того, щоб достатньо наїстись та продовжити бігти, Козі потрібно відвідати хоча б \(k\) клітинок із травою.

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

Ваша задача — порахувати мінімальну кількість клітинок, через які Козі потрібно пройти, щоб відвідати хоча б \(k\) клітинок з травою. Якщо це зробити неможливо, виведіть -1.

Вхідні дані

У першому рядку задано два натуральних числа \(n\) та \(k\) — розміри поля та мінімальна кількість клітинок з травою відповідно. В наступних \(n\) рядках задано поле, по \(n\) символів в кожному рядку (без пробілів). Цифра 1 позначає траву, а цифра 0 — бетон.

Вихідні дані

У єдиному рядку виведіть одне ціле число — мінімальну кількість клітинок, які Коза повинна відвідати для досягнення своєї цілі.

Обмеження

\(1 \le k \le 50\),

40% тестів: \(1 \le n \le 50\),

60% тестів: \(1 \le n \le 500\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 3 0101 0001 0100 0001	4

Примітки

У прикладі вище Козі оптимально відвідати 4 клітинки: \((1, 2)\), \((1, 3)\), \((1, 4)\), \((2, 4)\). По дорозі Коза з’їcть траву в 3 клітинках, чого достатньо, щоб наїстись.