Рассмотрим мага на позиции $$$i$$$. Чтобы посчитать сколько единиц урона нанесет $$$i$$$-й маг, нужно знать какими отрезками заклинаний покрывается этот маг. Пусть номер минимального отрезка, который содержит в себе $$$i$$$ равен $$$x$$$, тогда $$$i$$$-й маг нанесет $$$(x - 1) \cdot s_i$$$ единиц урона.
Воспользуемся техникой динамического программирования. Пусть $$$dp[i, msk] = minDamage$$$, $$$i$$$ — позиция мага, которого сейчас рассматриваем, $$$msk$$$ — число в троичной системе счисления, характеризующее отрезки.
Возможные переходы:
Ответ находится в $$$dp[n, msk]$$$, если $$$msk$$$ не содержит открытых отрезков.
Время работы: $$$\mathcal{O}(n \cdot 3^m \cdot m)$$$.