Мирко получил в подарок на свой день рождения квадратный стол N x N , где в каждой клетке записано неотрицательное целое число. К сожалению, некоторые числа кажутся Мирко слишком большими, поэтому он собирается положить на стол K фишек домино, которые закроют некоторые слишком большие числа. Точнее, он собирается положить фишки домино в соответствии со следующими правилами:

1. Каждая фишка домино покрывает две клетки, соседних по строчке или столбцу..

2. Фишки домино не накладываются друг на друга (но могут соприкасаться).

3. Сумма чисел на всех видимых (непокрытых) клетках минимальна.

Ваша задача - определить минимально возможную сумму чисел на видимых клетках. Тесты к задаче таковы, что на поле всегда можно положить K не накладывающихся друг на друга фишек домино.