CF2023B Skipping

It is already the year $ 3024 $ , ideas for problems have long run out, and the olympiad now takes place in a modified individual format. The olympiad consists of $ n $ problems, numbered from $ 1 $ to $ n $ . The $ i $ -th problem has its own score $ a_i $ and a certain parameter $ b_i $ ( $ 1 \le b_i \le n $ ). Initially, the testing system gives the participant the first problem. When the participant is given the $ i $ -th problem, they have two options: - They can submit the problem and receive $ a_i $ points; - They can skip the problem, in which case they will never be able to submit it. Then, the testing system selects the next problem for the participant from problems with indices $ j $ , such that: - If he submitted the $ i $ -th problem, it looks at problems with indices $ j < i $ ; - If he skipped the $ i $ -th problem, it looks at problems with indices $ j \leq b_i $ . Among these problems, it selects the problem with the maximum index that it has not previously given to the participant (he has neither submitted nor skipped it before). If there is no such problem, then the competition for the participant ends, and their result is equal to the sum of points for all submitted problems. In particular, if the participant submits the first problem, then the competition for them ends. Note that the participant receives each problem at most once. Prokhor has prepared thoroughly for the olympiad, and now he can submit any problem. Help him determine the maximum number of points he can achieve.

N/A

N/A

In the first test case, Prokhor can skip the first problem; then he will receive the problem with index $ b_1 = 2 $ . Prokhor can submit it and receive $ a_2 = 16 $ points. After that, the competition will end because Prokhor has already received all problems. Note that if Prokhor submits the first problem, he will receive $ a_1 = 15 $ points, but the competition will end immediately. In the second test case, Prokhor can skip the first problem; then he will receive the problem with index $ b_1 = 3 $ . Prokhor can submit it and receive $ a_3 = 100 $ points. After that, Prokhor will receive the second problem, which he can skip to receive the problem with index $ b_2 = 4 $ . Prokhor can submit the fourth problem and receive another $ a_4 = 100 $ points. After that, the competition ends because Prokhor has already received all problems with indices not exceeding $ 4 $ . Thus, Prokhor will receive a total of $ 200 $ points. In the third test case, Prokhor can submit the first problem and receive $ 100 $ points, after which the competition will end immediately.