Решение задачи Выращивание дерева с Codeforces

Садовод Лёша преподаёт школьникам олимпиадную информатику. На день учителя ребята подарили ему набор деревянных палочек, каждая из которых представляет собой отрезок целочисленной длины. Теперь Лёша хочет вырастить из них дерево.

Дерево представляет собой ломаную на плоскости, состоящую из всех подаренных ему палочек. Ломаная начинается в точке (0,0). Строя ломаную, Лёша может присоединять палочки в любом порядке, располагая каждую горизонтально или вертикально (то есть параллельно оси OX или OY). При этом не разрешается, чтобы две подряд идущие палочки лежали одновременно горизонтально или вертикально. Смотрите картинки ниже для уточнения деталей.

Лёша хочет сделать так, чтобы конец ломаной был как можно дальше от точки (0,0). Помогите ему вырастить дерево таким образом!

Заметим, что ломаная, в форме которой Леша вырастит дерево, может иметь самопересечения и самокасания, однако можно доказать, что оптимальный ответ не содержит ни самопересечений, ни самокасаний.