У вас есть \(n\) лампочек, пронумерованных целыми числами от \(1\) до \(n\). Лампочка \(i\) имеет два целочисленных параметра \(a_i\) и \(b_i\).
В каждый момент времени каждая лампочка находится в одном из трех состояний: она может быть выключена, включена или сломана.
Изначально все лампочки выключены. За одно действие вы можете включить одну выключенную лампочку (нельзя включать сломанные лампочки). За включение лампочки \(i\) вы получаете \(b_i\) очков. После каждого вашего действия происходит следующее:
- Пусть в данный момент включенными (сломанные лампочки не считаются) являются \(x\) лампочек. Все лампочки \(i\), для которых \(a_i \le x\), ломаются, независимо от того, включены они или выключены.
Обратите внимание, что сломанные лампочки никогда не считаются включенными, и что после поломки включенной лампочки очки, полученные за ее включение, не теряются.
Вы можете совершить произвольное число действий.
Найдите наибольшее количество очков, которое вы можете набрать.
Выходные данные
Для каждого набора входных данных выведите одно число — наибольшее количество очков, которое вы можете набрать.
Примечание
В первом наборе входных данных \(n = 4\). Единственный способ набрать наибольшее количество очков выглядит следующим образом:
- Вы включаете лампочку \(4\) и получаете \(b_4 = 13\) очков.
- Количество включенных лампочек равно \(1\), поэтому все лампочки, у которых \(a_i \le 1\), то есть лампочки \(2\), \(3\) и \(4\), ломаются. Лампа \(4\) больше не считается включенной и количество включенных лампочек становится равным \(0\).
- Вы можете включить только лампочку \(1\), так как все остальные лампочки сломаны. Вы получаете \(b_1 = 2\) очка.
- Количество включенных лампочек равно \(1\). Так как \(a_1 = 2\), лампочка \(1\) не ломается.
Всего вы получили \(13 + 2 = 15\) очков. Можно показать, что это наибольшее количество очков, которое можно набрать, следовательно ответ на первый набор входных данных равен \(15\).
Во втором наборе входных данных один из способов набрать наибольшее количество очков выглядит следующим образом:
- Первым действием вы включаете лампочку \(4\) и получаете \(2\) очка. После этого действия ни одна лампочка не ломается.
- Вторым действием вы включаете лампочку \(3\) и получаете \(5\) очков. После этого действия включены \(2\) лампочки. Так как \(a_3 \le 2\), лампочка \(3\) ломается.
- Третьим действием вы включаете лампочку \(1\) и получаете \(4\) очка.
- Четвертым действием вы включаете лампочку \(5\) и получаете \(3\) очка. После этого действия включенными являются \(3\) лампочки: \(1\)-я, \(4\)-я и \(5\)-я. Лампочки \(1\), \(2\), \(4\) и \(5\) одновременно ломаются, так как для них всех \(a_i \le 3\).
Всего вы получили \(2 + 5 + 4 + 3 = 14\) очков. Можно показать, что это наибольшее количество очков, которое можно набрать.
В третьем наборе входных данных один из способов набрать наибольшее количество очков выглядит следующим образом:
- Включить лампочку \(3\), получить \(4\) очка. Лампочки \(1\) и \(3\) ломаются.
- Включить лампочку \(2\), получить \(4\) очка.
- Включить лампочку \(6\), получить \(3\) очка. Лампочка \(6\) ломается.
- Включить лампочку \(4\), получить \(4\) очка.
- Включить лампочку \(5\), получить \(5\) очков. Лампочки \(2\), \(4\) и \(5\) ломаются.
Всего вы получили \(4 + 4 + 3 + 4 + 5 = 20\) очков. Можно показать, что это наибольшее количество очков, которое можно набрать.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
2 2
1 6
1 10
1 13
5
3 4
3 1
2 5
3 2
3 3
6
1 2
3 4
1 4
3 4
3 5
2 3
1
1 1
|
15
14
20
1
|