E. Ну-ка, покатились!
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

Входные данные

В первой строке входных данных записано целое число n (1 ≤ n ≤ 3000) — количество шариков. В следующих n строках даны описания шариков парами целых чисел xi, ci ( - 109 ≤ xi, ci ≤ 109). Числа разделяются пробелом. Каждое описание находится на отдельной строке. Никакие два шарика не имеют одинакового начального положения.

Выходные данные

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

Примеры
Входные данные
3
2 3
3 4
1 2
Выходные данные
5
Входные данные
4
1 7
3 1
5 10
6 1
Выходные данные
11