Задача “Видеосалон” (Рекуррентное соотношение с одним параметром)

Условие задачи: ссылка
Основная идея:  Для успешного решения задачи было бы неплохо знать подход к решению классической задачи “Рюкзак” на Динамическое программирование. Все решение сводится к заполнению трех массивов: s,ns,ms (авторские названия).
Массив s:
s[i] == 1, если можно набрать суммарное время i, используя один или несколько фильмов.
s[i] == 0, в противном случае.
Массив ns:
ns[i] – количество способов, которыми можно набрать суммарное время i одним или несколькими фильмами. ns[i] не равен нулю только в том случае, если s[i] не равно нулю.
Массив ms:
ms[i] == 1, если время i было промежуточным для получения бОльшего времени I.
ms[i] == 0, в противном случае.

Исходный код: здесь

P.S: Признаюсь долго приходило понимание решения этой задачи. Основные моменты: строка 35 и способ формирования ответа.