Задача . E. Рудольф и k мостов

Бернард любит ездить к Рудольфу в гости, но постоянно опаздывает. Проблема в том, что Бернард вынужден переплывать реку на пароме. Рудольф решил помочь своему другу решить эту проблему.

Река представляет собой клетчатое поле из \(n\) строк и \(m\) столбцов. На пересечении \(i\)-й строки и \(j\)-го столбца записано число \(a_{i,j}\) — глубина в соответствующей клетке. Все клетки первого и последнего столбцов соответствуют берегам реки, поэтому глубина в них \(0\).

Река может выглядеть так.

Рудольф может выбрать строку \((i,1), (i,2), \ldots, (i,m)\) и построить над ней мост. В каждой клетке строки он может установить опору для моста. Стоимость установки опоры в клетке \((i,j)\) равна \(a_{i,j}+1\). Опоры необходимо установить так, чтобы были выполнены следующие условия:

1. В клетке \((i,1)\) должна быть установлена опора;
2. В клетке \((i,m)\) должна быть установлена опора;
3. Расстояние между любой парой соседних опор должно быть не больше \(d\). Расстояние между опорами \((i, j_1)\) и \((i, j_2)\) равно \(|j_1 - j_2| - 1\).

Построить один мост это скучно. Поэтому Рудольф решил построить \(k\) мостов на последовательных строках реки, то есть выбрать некоторое \(i\) (\(1 \le i \le n - k + 1\)) и независимо построить по мосту на каждой из строк \(i, i + 1, \ldots, i + k - 1\). Помогите Рудольфу минимизировать суммарную стоимость установки опор.