Maximum Increasing Subsequence Energy Sum

You are given T test cases. For each test case, you are provided with an integer N representing the number of spells and a sequence of N integers representing the energies of these spells. Your task is to select a strictly increasing subsequence of spells such that the sum of the energies is maximized.

You can solve this problem using dynamic programming. Define a DP array where \(dp[i]\) represents the maximum sum of an increasing subsequence ending at index \(i\). The recurrence relation is given by:

\(dp[i] = \max_{0 \leq j < i \; \text{and} \; arr[j] < arr[i]} (dp[j]) + arr[i]\)

The answer for each test case is the maximum value in the DP array.

inputFormat

The input begins with an integer T, the number of test cases. Each test case is described as follows:

• An integer N, the number of spells.
• A line containing N space-separated integers representing the energies of the spells.

All input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing the maximum sum of energies of a strictly increasing subsequence.

All output should be written to standard output (stdout).

## sample

2
5
10 20 30 40 50
6
5 10 5 20 15 40

150
75

</p>