Profits by cars
Tag(s):

## Algorithms, Greedy Algorithms

Problem
Editorial
Analytics

You are a car seller. You have $N$ cars and the profit for each of the cars is given by an array $P$. The profit of cars are $P_1,\ P_2,\ P_3,\ ...,\ P_N$. Since you got a huge profit in the last month so you decide to get $(N-1)$ more sets of such cars. You already have one car. Now, you have $N^2$ cars. Basically, there are $N$ number of cars of each profit such as $N$ cars for profit $P_1$, $N$ cars of profit $P_2$, and so on up to $N$ cars of profit $P_N$.

You can perform the following operations any number of times:

• If the last car is sold for profit $P$, then you can sell a car for profit $P_c >P$ .

Note: You can select a car of any profit in the first operation as there are no cars that are sold earlier.

Find out the maximum profit that you can make.

For example, $N=4$ and prices are $P_1,\ P_2,\ P_3,\ P_4$. Since $N$ is 4, therefore you can have four sets of cars and the prices are $P_1,\ P_2,\ P_3,\ P_4,\ P_1,\ P_2,\ P_3,\ P_4 ,\ P_1,\ P_2,\ P_3,\ P_4 ,\ P_1,\ P_2,\ P_3,\ P_4$ .

See the sample explanation for more details.

Input format

• The first line contains a single integer $T$ denoting the number of test cases.
• The first line of each test case consists of an integer $N$.
• The second line consists of $N$ space-separated integers $P_1,\ P_2,\ P_3,\ ...,\ P_N$

Output format

For each test case, print a single integer denoting the maximum amount of profit that you can make.

Constraints

$1 \leq T \leq 100$

$1\leq N\leq 100000$

$1\leq P_i<=1e9 \forall i \in [1,N]$

Sum of $N$ over all test cases does not exceed $100000$

SAMPLE INPUT
1
3
1 2 3

SAMPLE OUTPUT
6
Explanation

Since N=3 here jetha will have 3 sets of cars so cars he will have are of profit 1,2,3,1,2,3,1,2,3.

He has three choices for the first car so suppose that he sell a car with profit 3 then he can not perform any operation as there is no car with profit greater than 3.Profit he makes is 3.

Suppose he sells a car with profit 2.On next operation he can sell a car for profit 3 as 3 is only available choice.After that he has to terminate.Profit he can make is 2+3=5.

If he sells a car at profit 1 then on next he has two choices {2,3} if he sells the next car at 3.He has to terminate and the profit he makes is 4.While If he sells a car at profit 2 on next day he can make another move and sell the car at price 3 so total profit:1+2+3=6 which is highest he can make.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

July Easy '20

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Arrays
• Basic Programming > Implementation
• Math > Combinatorics
• Algorithms > Dynamic Programming
• Algorithms > Dynamic Programming