Від вершини до підніжжя пагорба росте \(N\) старих дерев. Районна адміністрація вирішила з санітарною метою зрубати ці дерева, а щоб знизити вартість заходу перевезти все деревину на пилораму.

Дерева можуть бути перевезені лише в одному напрямку – вниз. Біля підніжжя пагорба знаходиться пилорама, а також дві додаткові пилорами можуть бути побудовані на пагорбі вздовж дороги. Ви повинні визначити, де найбільш вигідно побудувати ці пилорами, щоб мінімізувати вартість транспортування деревини. Перевезення 1 кілограма деревини на 1 метр коштує 1 копійку.

Формат вхідних даних

Перший рядок містить натуральне число \(𝑁\) – кількість дерев (\(1≤𝑁≤20000\)). Дерева занумеровані від 1 до \(𝑁\) з вершини пагорба.

Наступні \(𝑁\) рядків містять по два цілих числа \(𝑤_𝑖\) і \(𝑑_𝑖\) (\(1≤𝑤_𝑖,𝑑_𝑖≤10000\) ) – вага дерева номер \(𝑖\) і відстань між деревами \(𝑑_𝑖\) і \(d_{i+1}\) Останнє з цих чисел (\(𝑑_𝑛\) ) задає відстань від нижнього дерева до пилорами.

Формат вихідних даних

Виведіть одне число – мінімальну вартість.

Оцінювання

• Рішення для \(𝑁≤1000\) будуть оцінюватися в 40 балів при проходженні всіх тестів цієї групи.

Приклад вхідних даних

9
1 2
2 1
3 3
1 1
3 2
1 6
2 1
1 2
1 1

Приклад вихідних даних

26