GOOD NUMBERED CHOCOLATES

 

GOOD NUMBERED CHOCOLATES

You have a bag of N$N$ chocolates that you intend to eat. Eating chocolates makes you happy, but however, eating different number of chocolates in one sitting gives you different amounts of happiness. Formally, eating i$i$ number of chocolates, gives you hi$h_i$ amount of happiness.

Given the amounts of happiness you gain by eating i$i$ number of chocolates for all 1≤i≤N$1\le i\le N$, you wonder what is the maximum total happiness that you can obtain from the N$N$ chocolates.

Note that you are allowed to eat the same number of chocolates i$i$ multiple times as long as the remaining number of chocolates is not lesser than i$i$.

INPUT

The first line of input contains a single integer t$t$ (1≤t≤1000$1\le t\le 1000$) that denotes the number of test-cases. The next 2t$2t$ lines describe the test-cases.

The first line of each test-case contains a single integer N$N$ (1≤N≤1000$1\le N\le 1000$) denoting the total number of chocolates. The next line of each test-case contains N$N$ space-separated integers, the ith$i^{th}$ number denoting the amount of happiness gained by eating i$i$ chocolates, hi$h_i$ (1≤hi≤105$1\le h_i\le {10}^5$).

It is guaranteed that the sum of N$N$ across all test-cases does not exceed 1000$1000$.

OUTPUT

For each test-case, output a single integer - the maximum amount of happiness that can be obtained from N$N$ chocolates.

EXAMPLE

Sample 1 INPUT:

properties
2
8
3 5 8 9 10 17 17 20
8
1 5 8 9 10 17 17 20

Sample 1 OUTPUT:

text
24
22


#include <bits/stdc++.h>
using namespace std;
#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl
inline int power(int a, int b)
{
  int x = 1;
  while (b)
  {
    if (b & 1) x *= a;
    a *= a;
    b >>= 1;
  }
  return x;
}
template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
  const char* comma = strchr (names + 1, ',');
  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}
const int N = 200005;
int helper(vector<vector<int>>&dp,vector<int>&v,int i,int rem){
    if(i<=0 || rem==0)return 0;
    if(dp[i][rem]!=-1){return dp[i][rem];}
    if((rem-i)<0){
      return dp[i][rem]=helper(dp,v,i-1,rem);
    }
    int a=helper(dp,v,i-1,rem);
    int b=v[i-1]+ helper(dp,v,i,rem-i);
    return dp[i][rem]=max(a,b);
}
void solve() {
int n;
cin>>n;
vi v(n);
for (int i = 0; i < n; i++)
{
    cin>>v[i];
}
vector<vector<int>>dp(n+1,vector<int>(n+1,-1));
cout<<helper(dp,v,n,n)<<endl;



}
int32_t main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  clock_t z = clock();
  int t = 1;
  cin >> t; 
  while (t--) solve();


  return 0;
}