Задача на динамическое программирование

[miraina]

Столкнулась со следующей задачей:

В спортивном параде должны были идти две колонны спортсменов с флагами, но когда колонны уже выстроились перед выходом, оказалось, что ширины дорожки для двух колонн не хватит. Экстренно было принято решение совместить две колонны в одну. Сначала хотели пустить вперед первую колонну, а следом за ней вторую, но, посовещавшись, чтобы никого не обидеть, решили перемешать две колонны. При этом, чтобы улучшить эстетическую составляющую зрелища, чередование участников колонн должно было происходить так, чтобы сумма разностей высот соседних флагов была минимальна.

Зная высоты флагов и их очередность в каждой колонне по отдельности, определите какую минимальную сумму разностей высот соседних флагов могут получить организаторы шествия, объединив колонны, но не меняя порядок выхода участников каждой из них.

Ввод
3 3
1 5 3
2 2 6
Вывод
8

Перебор обычный - естественно не проходит. Решила, что это все-таки динамика. Всегда меня учили, что для динамики нужно выбрать базу и шаг, по которому идем. Помогите советом - как сделать оптимальнее и правильнее?

[venco]

Попробуйте динамику с тремя параметрами - оставшиеся длины колонн, и флаг какой колонны вышел последним.