Мирко получил в подарок на свой день рождения квадратный стол N x N , где в каждой клетке записано неотрицательное целое число. К сожалению, некоторые числа кажутся Мирко слишком большими, поэтому он собирается положить на стол K фишек домино, которые закроют некоторые слишком большие числа. Точнее, он собирается положить фишки домино в соответствии со следующими правилами:
1. Каждая фишка домино покрывает две клетки, соседних по строчке или столбцу..
2. Фишки домино не накладываются друг на друга (но могут соприкасаться).
3. Сумма чисел на всех видимых (непокрытых) клетках минимальна.
Ваша задача - определить минимально возможную сумму чисел на видимых клетках. Тесты к задаче таковы, что на поле всегда можно положить K не накладывающихся друг на друга фишек домино.
Первая строка содержит два целых числа: N ( 1 ≤ N ≤ 2000 ) - размер стола, и K ( 1 ≤ K ≤ 8 ) - количество фишек домино. Каждая из следующих N строк содержит N целых чисел (в диапазоне [0, 1000]) - числа в соответствующих клетках поля.
Выведите единственное целое число - минимально возможную сумму чисел в клетках после установки фишек домино.
Решения, работающие при K ≤ 5 , будут оцениваться в 70 баллов.
3 1 2 7 6 9 5 1 4 3 8
31
4 2 1 2 4 0 4 0 5 4 0 3 5 1 1 0 4 1
17