На улице уже \(3024\) год, идеи для задач давно закончились, а олимпиады теперь проходят в изменённом индивидуальном формате. Олимпиада состоит из \(n\) задач, пронумерованных от \(1\) до \(n\). \(i\)-я задача имеет свою стоимость \(a_i\) и некоторый параметр \(b_i\) (\(1 \le b_i \le n\)).
Изначально тестирующая система выдаёт участнику первую задачу. Когда участнику выдают \(i\)-ю задачу, у него есть два варианта:
- Либо он сдаёт задачу и получает \(a_i\) баллов;
- Либо он может пропустить задачу, тогда он никогда не сможет её сдать.
Далее тестирующая система выбирает для участника следующую задачу среди задач с номерами \(j\), такими что:
- Если он сдал \(i\)-ю задачу, она смотрит на задачи с номерами \(j < i\);
- Если он пропустил \(i\)-ю задачу, она смотрит на задачи с номерами \(j \leq b_i\).
Среди этих задач она выбирает задачу с максимальным номером, которую она ранее не выдавала участнику (до этого он её не сдавал и не пропускал). Если такой задачи нет, то соревнование для участника завершается, и его результат равен сумме баллов за все сданные задачи. В частности, если участник сдаёт первую задачу, то соревнование для него завершается. Заметьте, что участник получает каждую задачу максимум один раз.
Прохор тщательно готовился к олимпиаде, и теперь он может сдать любую задачу. Помогите ему определить, какое максимальное количество баллов он может получить.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — максимальное количество баллов, которое может получить Прохор.
Примечание
В первом наборе входных данных Прохор может пропустить первую задачу, тогда он получит задачу с номером \(b_1 = 2\). Прохор может сдать её и получить \(a_2 = 16\) баллов. После этого соревнование завершится, потому что Прохор уже получал все задачи. Обратите внимание, что если Прохор сдаст первую задачу, то он получит \(a_1 = 15\) баллов, но соревнование сразу завершится.
Во втором наборе входных данных Прохор может пропустить первую задачу, тогда он получит задачу с номером \(b_1 = 3\). Прохор может сдать её и получить \(a_3 = 100\) баллов. После этого Прохор получит вторую задачу, которую он может пропустить и получить задачу с номером \(b_2 = 4\). Прохор может сдать четвёртую задачу и получить ещё \(a_4 = 100\) баллов. После этого соревнование завершается, потому что Прохор уже получал все задачи с номерами, не превосходящими \(4\). Таким образом, суммарно Прохор получит \(200\) баллов.
В третьем наборе входных данных Прохор может сдать первую задачу и получить \(100\) баллов, после чего соревнование сразу завершится.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
15 16
2 1
5
10 10 100 100 1000
3 4 1 1 1
3
100 49 50
3 2 2
4
100 200 300 1000
2 3 4 1
|
16
200
100
1000
|