Пусть, например у нас N=3, M=12
Стоимость 1-3 минут равна 2, стоимость 4 минуты равна 3, стоимость 5-INF минут равна 10.
Изначально f(0)=0, g(0)=0.
Считаем f(1):
f(1)=f(0)+g(1)=2
Для первой очереди делаем счетчик количества минут равным 1 и добавляем туда число 2-2*0=0.
Состояние очередей:
1) {2}, счетчик 1
2)-... {}, счетчики 0
Состояние первой очереди {2} означает что когда мы будем считать f(2) у нас f(1)+g(1) будет равно 2+счетчик*цену=2+1*2=4.
Считаем f(2):
f(2)=min(f(0)+g(2),f(1)+g(1))=4
Минимальный из предыдущих элементов это 4.
Для первой очереди увеличиваем счетчик на 1 и добавляем туда число 4-2*1=2.
Состояние очередей:
1) {2,2}, счетчик 2
2)-... {}, счетчики 0
Состояние первой очереди {2,2} и счетчик 2 означает что когда мы будем считать f(3) у нас f(1)+g(2) будет равно 2+счетчик*цену=2+2*2=6. Аналогично f(2)+g(1)=6.
Считаем f(3):
f(3)=min(f(0)+g(3),f(1)+g(2),f(2)+g(1))=6.
Минимальный из предыдущих элементов это 6.
Для первой очереди увеличиваем счетчик на 1 и добавляем туда число 6-2*2=2.
Состояние очередей:
1) {2,2,2}, счетчик 3
2)-... {}, счетчики 0
Состояние первой очереди {2,2,2} и счетчик 3 означает что когда мы будем считать f(4) у нас f(1)+g(3) будет равно 2+счетчик*цену=2+3*2=8. Аналогично f(2)+g(2)=f(3)+g(1)=8.
Считаем f(4):
f(4)=min(f(0)+g(4),f(1)+g(3),f(2)+g(2),f(3)+g(1))=8.
Минимальный из предыдущих элементов это 8.
Из первой очереди достаем элемент 2, находим его реальное значение, т.е. 2+3*2=8, переносим его во вторую очередь, прибавляем там счетчик 1 и добавляем туда число 8-3*0=8.
У первой очереди увеличиваем счетчик на 1 и добавляем туда 8-3*2=2.
Состояние очередей:
1) {2,2,2}, счетчик 4
2) {8}, счетчик 1
3)-... {}, счетчики 0
Считаем f(5):
f(5)=min(f(0)+g(5),...)=10.
Из первой очереди достаем элемент 2, находим его реальное значение, т.е. 2+4*2=10, переносим его во вторую очередь и добавляем туда число 10-3*1=7.
Одновременно с этим достаем элемент 8 из второй очереди, находим его реальное значение, т.е. 8+3*1=11, переносим его в третью очередь и добавляем туда число 11-10*0=11.
Увеличиваем счетчики очередей 1,2,3.
Состояние очередей:
1) {2,2,2}, счетчик 5
2) {7}, счетчик 2
3) {11}, счетчик 1
Считаем f(6):
f(6)=min(f(0)+g(6),...)=12.
...
Теперь состояние очередей:
1) {2,2,2}, счетчик 6
2) {6}, счетчик 3
3) {11,3}, счетчик 2
Это значит, что при подсчете f(7) у нас будет:
h(1)=f(1)+g(6)=11+2*10=31
h(2)=f(2)+g(5)=3+2*10=23
h(3)=f(3)+g(4)=6+3*3=15
h(4)=f(4)+g(3)=2+6*2=14
h(5)=f(5)+g(2)=2+6*2=14
h(6)=f(6)+g(1)=2+6*2=14
Дальше, очевидно, f(x) будет >12, поэтому ответ для данного теста будет равен 6.