Это простая версия задачи. Разница в версиях заключается в ограничениях на \(a_i\). Вы можете делать взломы, только если обе версии задачи решены.
Маленький Дорми недавно получил головоломку от своего друга, и ему требуется ваша помощь для ее решения.
Головоломка состоит из вертикальной доски с \(n\) строками и \(m\) столбцами, некоторые ячейки на доске пустые, а некоторые заполнены песком. Также даны \(m\) неотрицательных целых чисел \(a_1,a_2,\ldots,a_m\) (\(0 \leq a_i \leq n\)). В этой версии задачи \(a_i\) равно числу ячеек с песком в столбце \(i\).
Если стукнуть по ячейке, заполненной песком, то весь песок из ячейки упадет вниз на счетчик песка своего столбца (в каждом столбце есть счетчик песка). Когда песок падает, весь песок, в какой-либо момент находящийся в соседней ячейке с падающим песком, тоже начинает падать. А именно, если песок начинает падать из ячейки \((i,j)\), то он будет падать через все ячейки ниже в этом столбце, включая саму ячейку \((i,j)\), вызывая падения во всех ячейках, соседних к какой-либо ячейке на пути. Соседними к ячейке \((i,j)\) являются ячейки \((i-1,j)\), \((i,j-1)\), \((i+1,j)\) и \((i,j+1)\) (если такие существуют). Обратите внимание, что новые падающие ячейки песка тоже вызывают падение соседних ячеек.
За одну операцию вы можете стукнуть по одной ячейке с песком. Головоломка решена, если на счетчике песка в \(i\)-м столбце находится не менее \(a_i\) ячеек с песком для всех столбцов от \(1\) до \(m\).
Вам нужно определить минимальное количество операций, необходимое, чтобы решить головоломку. Маленький Дорми никогда не даст вам головоломку, которую нельзя решить.
Примечание
В примере \(1\) можно стукнуть ячейку в левом верхнем углу, ячейку во втором сверху ряду в четвертом столбце слева, и ячейку в третьем ряду сверху в шестом столбце слева. Тогда упадет необходимое количество песка в каждом столбце. Можно показать, что нельзя сделать меньше \(3\) операций, и поэтому ответ равен \(3\). Ниже приведен рисунок к первому примеру.
В примере \(2\) можно стукнуть по ячейке в верхнем ряду в правом столбце, и весь песок в таблице упадет вниз. Поэтому ответ равен \(1\). Ниже приведен рисунок ко второму примеру.
