Задача №113913. Иннофон
Одна телекоммуникационная компания планирует в скором будущем выпустить на рынок сразу два инновационных смартфона. Эти смартфоны будут называться «иннофон» и «иннофон плюс». Устройства уже полностью готовы к производству, и последняя задача, которую необходимо решить руководству компании, — выбрать оптимальную цену для каждого из смартфонов.
Аналитики компании провели исследование, в результате которого построили следующую модель. Всего есть n потенциальных покупателей инновационных смартфонов. Для принятия решения i -й покупатель использует следующий алгоритм, характеризующийся двумя числами a i и b i ( a i ≥ b i ):
- если цена на «иннофон плюс» не больше a i , то он покупает «иннофон плюс»,
- иначе, если цена на «иннофон» не больше b i , то он покупает «иннофон»,
- иначе он не покупает ничего.
Руководство компании хочет установить цены на «иннофон» и «иннофон плюс» таким образом, чтобы обе цены были целым числом, цена «иннофона» была не больше цены «иннофона плюс», и при этом суммарная стоимость проданных смартфонов была максимальна.
Требуется написать программу, которая находит максимально возможную суммарную стоимость проданных смартфонов.
В первой строке содержится целое число n ( 1 ≤ n ≤ 150 000 ) — число потенциальных покупателей.
В следующих n строках содержатся по два целых числа a i , b i ( 0 ≤ b i ≤ a i ≤ 10 9 ) — характеристики алгоритма выбора телефона покупателем с номером i .
Выведите одно целое число — максимальную возможную суммарную стоимость проданных смартфонов.
В первом примере для достижения максимальной суммы следует назначить цены на «иннофон» и «иннофон плюс» равными 40 и 70 соответственно. Тогда первый и пятый покупатель купят «иннофон плюс», второй и третий покупатель купят «иннофон», четвертый покупатель не купит ничего. Суммарная стоимость проданных смартфонов будет 70 + 40 + 40 + 0 + 70 = 220 .
Во втором примере нужно сделать цену «иннофона плюс» равной 50. Цена на «иннофон» при этом не важна.
5 80 20 60 50 40 40 15 10 70 30
220
1 50 0
50