시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB444100.000%

문제

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

Аналитики компании провели исследование, в результате которого построили следующую модель. Всего есть $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$.

출력

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

서브태스크

번호배점제한
19

$n \le 100$, $b_i \le a_i \le 100$

210

$n \le 300$

316

$n \le 3000$

411

$n \le 10^5$, $b_i = 0$

516

$n \le 10^5$, $a_i = b_i$

67

$n \le 50\,000$

77

$n \le 75\,000$

88

$n \le 100\,000$

98

$n \le 125\,000$

108

$n \le 150\,000$

예제 입력 1

5
80 20
60 50
40 40
15 10
70 30

예제 출력 1

220

예제 입력 2

1
50 0

예제 출력 2

50

힌트

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

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

채점 및 기타 정보

  • 예제는 채점하지 않는다.