На числовой прямой, направленной слева направо, находятся n шариков с координатами x₁, x₂, ..., x_n. Размеры шариков будем считать бесконечно малыми, то есть в этой задаче каждый из них будем считать материальной точкой. Вы можете в некоторые из них воткнуть булавки, стоимость втыкания в i-ый шарик равна c_i, число c_i может быть отрицательным. После того, как вы выберите и воткнете нужные вам булавки, шарики начнут катиться влево по правилу: если в шарик воткнута булавка, то он не двигается, иначе шарик катится до ближайшего другого шарика, в который булавка воткнута, где заканчивает свое движение. Если слева от данного неприколотого шарика не существует приколотого, то считается, что шарик укатывается бесконечно влево, и вы заплатите за это бесконечно большой штраф. В случае, если никакой шарик не укатился бесконечно влево, то штраф будет состоять из двух слагаемых:

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

Ваша задача — выбрать и приколоть некоторые шарики так, чтобы штраф, который вы заплатите, был как можно меньше.