eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Паруса

Паруса

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Строиться новый пиратский парусник. У парусника есть N мачт, разделенных на единичные сегменты, при этом высота мачты равна количеству сегментов. На каждой мачте размещено некоторое количество парусов, каждый из которых занимает один сегмент. Паруса на мачте могут быть размещены произвольным образом по сегментах, но в каждом сегменте может быть размещен только один парус.

Разные расположения парусов обеспечивают разную тягу, когда на них дует ветер. Парус, если он находится перед другими парусами на той же высоте, получает меньше ветра и дает меньше тяги. Для каждого паруса определим показатель его неэффективности как суммарное количество парусов, размещенных за этим парусом на той же высоте. Обратите внимание, что "перед" и "за" определяется относительно расположения корабля: на рисунке "перед" обозначает слева, "за" - справа.

Общий показатель неэффективности размещения парусов - это сумма показателей неэффективности каждого из парусов.

Задание

Напишите программу, которая по заданной высоте и количеству парусов на каждой из N мачт, определяет наименьший возможный общий показатель неэффективности.

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

Первая строка входных данных содержит целое число N (2 ≤ N ≤ 100 000), количество мачт на корабле.

Каждая из последующих N строк содержит по два целых числа H и K (1 ≤ H ≤ 100 000, 1 ≤ K ≤ H), высоту соответствующей мачты и количество парусов на ней. Мачты заданы в порядке от носа к корме корабля.

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

Выход должен состоять из одного целого числа - минимально возможного общего показателя неэффективности.

Пример

Входные данные #1
6
3 2
5 3
4 1
2 1
4 3
3 2

Выходные данные #1
10
Источник IOI-2007, День 1