Rotten Ropes#6840
Suppose we have ropes of equal length and we want to use them to lift some heavy object. A tear-off weight is associated to each rope, that is, if we try to lift an object, heavier than with that rope, it will tear off. But we can fasten a number of ropes to the heavy object (in parallel), and lift it with all the fastened ropes. When using ropes to lift a heavy object with weight , we assume that each of the ropes, regardless of its tear-off weight, is responsible for lifting a weight of . However, if w/k > t for some rope with tear-off weight of , that rope will tear off.
For example, three ropes with tear-off weights of , , and , when all three are fastened to an object, can not lift an object with weight more than , unless the weaker one tears-off. But the second rope, may lift by itself, an object with weight at most .
Given the tear-off weights of ropes, your task is to find the weight of the heaviest object that can be lifted by fastening a subset of the given ropes without any of them tearing off.
The first line of the input file contains a single integer (1 \leq t \leq 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer (1 \leq n \leq 1000) which is the number of ropes. Following the first line, there is a single line containing integers between and which are the tear-off weights of the ropes, separated by blank characters.
Each line of the output file should contain a single number, which is the largest weight that can be lifted in the corresponding test case without tearing off any rope chosen.
Example 1