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

Обмеження: 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 клітинках, чого достатньо, щоб наїстись.