Задача №3370. Две лесопилки
От вершины до подножья холма растет \(N\) старых деревьев. Районная администрация решила в санитарных целях срубить эти деревья, а чтобы снизить стоимость мероприятия перевезти все древесину на лесопилки.
Деревья могут быть перевезены только в одном направлении – вниз. У подножья холма находится лесопилка, а также две дополнительные лесопилки могут быть построены на холме вдоль дороги. Вам предстоит определить, где наиболее выгодно построить эти лесопилки, чтобы минимизировать стоимость транспортировки древесины. Перевозка 1 килограмма древесины на 1 метр стоит 1 копейку.
Первая строка входного файла содержит натуральное число \(N\) – количество деревьев (\(1 \leq N \leq 20000\)). Деревья занумерованы от \(1\) до \(N\) начиная с вершины холма. Следующие \(N\) линий содержат по два целых числа \(w_i\) и \(d_i\) (\(1 \leq w_i, d_i \leq 10000\)) – вес дерева номер \(i\) и расстояние между деревьями \(d_i\) и \(d_{i+1}\). Последнее из этих чисел (\(d_n\)) задает расстояние от нижнего дерева до лесопилки.
Выведите единственное число – минимальную стоимость.
Решения, работающие для \(N \le 1000\) будут оцениваться в 40 баллов при прохождении всех тестов этой группы. Остальные баллы начисляются по тестам независимо.
9 1 2 2 1 3 3 1 1 3 2 1 6 2 1 1 2 1 1
26