Иннофон

면접 대비

시간 제한5초메모리 제한512 MB

요약

일반 가격 P와 플러스 가격 Q를 P ≤ Q가 되도록 정수로 정해, Q ≤ a_i이면 플러스, 그렇지 않고 P ≤ b_i이면 일반, 둘 다 아니면 아무것도 사지 않는 n명의 구매로 얻는 총 매출을 최대로 만든다.

난이도: 보통10점 중 6점
유형: 정렬, 그리디, 배열, 누적 합
정답자: 아직 제출이 없습니다

문제

Одна телекоммуникационная компания планирует в скором будущем выпустить на рынок сразу два инновационных смартфона. Эти смартфоны будут называться <<иннофон>> и <<иннофон плюс>>. Устройства уже полностью готовы к производству, и последняя задача, которую необходимо решить руководству компании, --- выбрать оптимальную цену для каждого из смартфонов.

Аналитики компании провели исследование, в результате которого построили следующую модель. Всего есть $n$ потенциальных покупателей инновационных смартфонов. Для принятия решения $i$ -й покупатель использует следующий алгоритм, характеризующийся двумя числами $a\_i$ и $b\_i$ ( $a\_i \geq b\_i$ ):

если цена на <<иннофон плюс>> не больше $a\_i$ , то он покупает <<иннофон плюс>>,
иначе, если цена на <<иннофон>> не больше $b\_i$ , то он покупает <<иннофон>>,
иначе он не покупает ничего.

Руководство компании хочет установить цены на <<иннофон>> и <<иннофон плюс>> таким образом, чтобы обе цены были целым числом, цена <<иннофона>> была не больше цены <<иннофона плюс>>, и при этом суммарная стоимость проданных смартфонов была максимальна.

Требуется написать программу, которая находит максимально возможную суммарную стоимость проданных смартфонов.

입력

В первой строке содержится целое число $n$ ( $1 \leq n \leq 150\\,000$ ) --- число потенциальных покупателей.

В следующих $n$ строках содержатся по два целых числа $a\_i$ , $b\_i$ ( $0 \leq b\_i \leq a\_i \leq 10^9$ ) --- характеристики алгоритма выбора телефона покупателем с номером $i$ .

출력

Выведите одно целое число --- максимальную возможную суммарную стоимость проданных смартфонов.

힌트

В первом примере для достижения максимальной суммы следует назначить цены на <<иннофон>> и <<иннофон плюс>> равными 40 и 70 соответственно. Тогда первый и пятый покупатель купят <<иннофон плюс>>, второй и третий покупатель купят <<иннофон>>, четвертый покупатель не купит ничего. Суммарная стоимость проданных смартфонов будет $70+40+40+0+70=220$ .

Во втором примере нужно сделать цену <<иннофона плюс>> равной 50. Цена на <<иннофон>> при этом не важна.

예제2

예제 1
입력
```
5
80 20
60 50
40 40
15 10
70 30
```
예상 출력
```
220
```
예제 2
입력
```
1
50 0
```
예상 출력
```
50
```