tanya-and-lassi

Your friend Tanya has recently launched a new company producing a very tasty version of India traditional drink called Lassi. 

It has become very popular, so there are a lot of customers who want to buy it. Recently, she prepared L liters of Lassi ready to sell. Moreover, his marketer sent her a list of L integers corresponding to prices for which bottles of sizes 1, 2, 3, ..., L can be sold. 

Since Tanya is good at producing drinks, but not as good as you with algorithms, she asked you to help her to get the maximum possible profit. In more details, you have to decide what is the maximum profit she can get by producing bottles from available L liters of Lassi and selling them to customers for prices given by the marketer. Notice that Tanya can produce any number of bottles of any integer size in a range [1, L], however, she gets money only for bottles full of Lassi. 

In one test file, your task is to handle T instances of the above problem.

Constraints:

1 ≤ T ≤ 10  
1 ≤ L ≤ 10000  
price for any bottle is a positive integer not greater than 10^6

Input format:

In the first line there is one integer T denoting the number of cases to solve. Each of these test cases is given by 2 consecutive lines. In the first of them, there is a single integer L denoting the number of available liters of Lassi. In the second one, there are L integers denoting the prices for which bottles of size 1, 2, 3, ..., L can be sold.

Output format:

In one line, output the maximum profit which Tanya can get by selling L liters of Lassi for given prices.

SAMPLE INPUT
1
3
2 5 6

SAMPLE OUTPUT
7

Explanation

There is one test case to handle. Tanya has 3 liters of Lassi and for a 1 liter bottle she can get a price 2, for 2 liters bottle a price 5, and for 3 liters bottle a price 6. The maximum profit she can achieve is 7. This is possible if she decides to sell one 2 liters bottle and one 1 liter bottle.

Source: hackerearth | Difficulty: EASY
Tags: Dynamic programming


Solutions: