Цивілізація

Limits: 2 sec., 256 MiB

Уявіть собі острів, на якому живуть древні племена. Спочатку острів був дуже рідко заселений, але з плином часу людська цивілізація заволоділа ним.

Формально будемо розглядати острів, як прямокутник зі сторонами \(n\) та \(m\). Також для простоти будемо вважати, що кожен квадрат \(1 \times 1\) цього прямокутника в деякий момент часу або повністю заселений, або повністю безлюдний. Відомо, що якщо незаселений квадрат межує із заселеним, то через рік він сам стане заселений. Два квадрати межують один з одним, якщо вони мають спільну сторону.

Вам відома початкова ситуація на острові. Необхідно знайти кількість заселених квадратів через \(k\) років.

Input

У першому рядку містяться три цілих числа \(n\), \(m\) та \(k\) — сторони прямокутника та кількість років.

Кожен із наступних \(n\) рядків містить \(m\) цілих чисел. \(j\)-ий елемент \(i\)-го рядка рівний 1, якщо відповідний квадрат є заселеним, або рівний 0 в протилежному разі.

Output

У єдиному рядку виведіть ціле число — кількість заселених квадратів через \(k\) років.

Constraints

\(1 \le n, m \le 100\),

\(0 \le k \le 10^6\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 4 1 0 1 0 0 1 0 0 0 0 0 0 1	9

Notes

Розмір деяких вхідних файлів є більшим за 1 МБ, тому зверніть увагу на функції, які ви використовуєте для зчитування даних. Переконайтесь у тому, що вони є достатньо швидкими.