Задача №111136. Паруса
Сомалийские пираты захватили парусный корабль. На корабле есть N мачт, каждая из которых разбита на сегменты — высота мачты задается количеством сегментов в ней. На каждой мачте находится ряд парусов и каждый парус прикреплен к одному сегменту мачты. Паруса на мачте могут быть произвольно распределены между сегментами, но к каждому сегменту может быть прикреплен только один парус.
Различные конфигурации парусов дают разную тягу, создаваемую ветром. Паруса, находящиеся ближе к носу, чем другие паруса на той же высоте, дают меньшую тягу. Для каждого из парусов определим неэффективность, как количество парусов, находящихся ближе к корме и располагающихся на той же высоте. На рисунке нос находится слева, а корма — справа.
Суммарная эффективность конфигурации равна сумме неэффективностей всех парусов. В приведенном на рисунке примере, у корабля 6 мачт высотами 3, 5, 4, 2, 4 и 3 считая с носа (слева направо). Показанное распределение парусов дает суммарную неэффективность 10. Неэффективность каждого паруса написана на нем. Флаг на неэффективность не влияет, он нарисован для красоты.
Напишите программу, которая по данной высоте и количеству парусов на каждой из N мачт, определяет наименьшую суммарную неэффективность.
Первая строка входного файла содержит число N (2 ≤ N ≤ 100 000), количество мачт на корабле. Каждая из следующих N строк содержит два числа H и K (1 ≤ H ≤ 100 000, 1 ≤ K ≤ H), высоту мачты и количество парусов на ней. Мачты перечислены от носа к корме.
Выведите одно число — наименьшую возможную суммарную неэффективность.
6
3 2
5 3
4 1
2 1
4 3
3 2
10