长跳跃 - 代码源竞赛平台

题目描述

蜗蜗站在一排长度为 $n$ 的格子上，格子编号从 1 到 $n$。第 $i$ 个格子上写着一个整数 $a_i$。

如果蜗蜗站在第 $i$ 个格子上，他只能跳到第 $i+a_i$ 个格子，并获得 $a_i$ 分。如果跳跃后超出最后一个格子，训练立即结束。

请你求出从任意一个格子出发时，蜗蜗能够获得的最大总分。

输入格式

第一行包含一个整数 T，表示测试用例数量。

对于每组测试用例：

• 第一行包含一个整数 $n$；
• 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对于每组测试用例，输出一行一个整数，表示能够获得的最大总分。

样例

1
5
2 3 1 1 1

5

样例解释

从第 1 个格子出发时，可以依次跳到第 3、第 4、第 5 个格子，获得 $2+1+1+1=5$ 分。

数据范围

对于 100% 的数据，保证 $1\le T\le1000$，所有测试用例的 $n$ 之和不超过 $2\times10^5$，$1\le a_i\le n$。