| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 512 MB | 92 | 14 | 7 | 10.938% |
Одна телекоммуникационная компания планирует в скором будущем выпустить на рынок сразу два инновационных смартфона. Эти смартфоны будут называться <<иннофон>> и <<иннофон плюс>>. Устройства уже полностью готовы к производству, и последняя задача, которую необходимо решить руководству компании, --- выбрать оптимальную цену для каждого из смартфонов.
Аналитики компании провели исследование, в результате которого построили следующую модель. Всего есть $n$ потенциальных покупателей инновационных смартфонов. Для принятия решения $i$-й покупатель использует следующий алгоритм, характеризующийся двумя числами $a_i$ и $b_i$ ($a_i \geq 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$.
Выведите одно целое число --- максимальную возможную суммарную стоимость проданных смартфонов.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 9 | $n \le 100,ドル $b_i \le a_i \le 100$ |
| 2 | 10 | $n \le 300$ |
| 3 | 16 | $n \le 3000$ |
| 4 | 11 | $n \le 10^5,ドル $b_i = 0$ |
| 5 | 16 | $n \le 10^5,ドル $a_i = b_i$ |
| 6 | 7 | $n \le 50,000円$ |
| 7 | 7 | $n \le 75,000円$ |
| 8 | 8 | $n \le 100,000円$ |
| 9 | 8 | $n \le 125,000円$ |
| 10 | 8 | $n \le 150,000円$ |
5 80 20 60 50 40 40 15 10 70 30
220
1 50 0
50
В первом примере для достижения максимальной суммы следует назначить цены на <<иннофон>> и <<иннофон плюс>> равными 40 и 70 соответственно. Тогда первый и пятый покупатель купят <<иннофон плюс>>, второй и третий покупатель купят <<иннофон>>, четвертый покупатель не купит ничего. Суммарная стоимость проданных смартфонов будет 70ドル+40+40+0+70=220$.
Во втором примере нужно сделать цену <<иннофона плюс>> равной 50. Цена на <<иннофон>> при этом не важна.