Метод ветвей и границ для задачи "Багдадский вор"

[Zavoorchik]

Здравствуйте!
Помогите, пожалуйста! Необходимо решить задачу "Багдадский вор" методом ветвей и границ. Методом динамического программирования я решил, а с этим никак не получается. Хотя бы с чего начать и в какую сторону двигаться.
Сама задача:
В высотном здании (150 этажей) Багдадского банка возник пожар. Огонь распространяется со скоростью 1 этаж в минуту. В здании имеется лифт, который движется со скоростью 10 этажей в минуту и застревает, если проходит через этаж, захваченный огнем. В момент начала пожара лифт стоит на первом этаже и там же находится знаменитый багдадский вор, желающий вынести из банка как можно больше золотых монет. Он знает номера этажей, на которых хранятся монеты, и точные их количества на каждом таком этаже. Для поиска монет на этаже и переноса их в лифт ему требуется полторы минуты.
Написать программу, выявляющую максимально возможное количество монет, которое может вынести вор, и порядок его действий. Исходные данные для программы: номер этажа, где начался пожар, и последовательность 149 чисел - количества монет на каждом этаже (на первом этаже монет нет).
Спасибо!