P10381 "HOI R1" Mixed Contest Selection Comparison

You are right, but when Little $\iiint$ was playing CF, he mistook Earn or Unlock as the weird parody below, wasted 2 hours, and had to leave with regret. Hope everyone can take this as a warning.

Given an array $a$ of length $n$, initially only $a_1$ is unlocked. Now there is an integer $i$ with initial value $1$. Little $\iiint$ plays a game on this array: - If $a_i$ is not unlocked, the game ends. - Otherwise, he can either set $a_{i+1\sim i+a_i}$ to unlocked, or gain $a_i$ coins (if $a_i=0$ then he cannot unlock any element), and then increase $i$ by $1$. Please find the maximum number of coins you can obtain after the game ends.

**This problem has multiple test cases.** The first line contains an integer $T$, the number of test cases. For each test case, the first line contains a positive integer $n$. The next line contains $n$ non-negative integers $a_{1\sim n}$.

For each test case, output one number per line, representing the answer.

#### Sample 1 Explanation For the first test case, you can unlock $a_2$, then gain $a_2$ coins. For the third test case, you cannot unlock $a_2$, so you can only gain $0$ coins. For the second test case, you can unlock $a_2,a_3$ and gain $9$ coins. #### Sample 2 Explanation Using positions $1,2,3,6$ for unlocking is the optimal strategy. #### Constraints For $100\%$ of the data, $1\le n\le10^5$, $0\le a_i\le10^5$, $T\le 5$. |Test Point ID|$n\leq$|$a_i\leq$|$T=$|Special Property| |:-:|:-:|:-:|:-:|:-:| |$1$|$10$|$0$|$1$|/| |$2\sim3$|$10$|$5$|$1$|/| |$4\sim5$|$600$|$600$|$1$|/| |$6\sim8$|$5000$|$5000$|$1$|/| |$9\sim10$|$10^5$|$5$|$5$|/| |$11\sim12$|$5\times10^4$|$10^5$|$5$|$a_i>n$| |$13\sim20$|$10^5$|$10^5$|$5$|/| Translated by ChatGPT 5