FRAKTAL - konkurs programistyczny

Firma "Metrax" zajmuje się wypiekaniem oraz sprzedażą pysznego ciasta zwanego metrowcem. We firmowym piecu można wypiec ciasto o długości n centymetrów. Ciasto może być pocięte na różnej długości kawałki. Najkrótszy może mieć długość 1cm a najdłuższy może mieć długość całego ciasta czyli n cm. Wiadomo, że cena ciasta o długości x może się różnić od ceny ciasta o długości y. Twoim zadaniem jest określenie, ile firma "Metrax" może zarobić najwięcej przy minimalnej liczbie kawałków.

Wejście

W pierwszym wierszu jedna liczba t określająca liczbę zestawów danych (t < 101).

Specyfikacja każdego zestawu danych.

W pierwszym wierszu jedna liczba n określająca długość metrowca (n < 1001). 

W drugim wierszu n liczb z zakresu [1..1000] takich, że i-ta liczba określa zarobek za ciasto o długości i.

Wyjście

Dla każdego zestawu po dwie liczby. Pierwsza określa maksymalny zarobek, jaki uzyska firma "Metrax", druga minimalną liczbę kawałków.

Przykład

Wejście:
3
5
1 1 4 7 7
5
1 1 3 4 4
6
1 2 3 3 3 4


Wyjście:
8 2
5 2
6 2