beecrowd | 1579

Transport of Solar Panels

By Neilor Tonin, URI BR Brazil

Timelimit: 1

In the last years, some companies has been very actuating in producing energy based on solar panels. Obviously the most appropriate place for it is the deserts. In the Mojave Desert, United States, several plants have been installed for solar power generation, such as the Nellis solar power plant, located on Nellis Air Force Base in Clark County, Nevada. This plant generates more than 30 million kilowatt hours of electricity per year. The project of 100 million U.S. dollars started the production of energy in late 2007, the plant is powered by 72,000 solar panels tracking the sun covering 140 acres. Apart from Nellis, other power plants such as Sierra Sun Tower, Copper Mountain Solar One and others were built in the same desert.

Spain already uses a solar plant in the Sahara Desert that was built by Solar Millennium. The project was so successful that now other companies are starting new projects in this region to generate energy for Europe.

Well, you own a transport company with many trucks and was hired by the company to transport Delta Solar solar panels in the Sahara. The panels have different sizes and weights related to the structure of each set of panels, which changes according to the location where they are to be installed. The transport them must be done in the correct sequence, which is exactly the sequence in which they appear on the entry.

The calculation of shipping is done according to the weight of their trucks and transported by the distance that trucks should go panels. It was agreed that every day you enter the amount of trucks available (this changes because some go to maintenance, new ones arrive, etc.) and a charge of Solar Delta will try to separate the loads to minimize the transportation value, since for initial hit, will pay the freight using as reference the heaviest load carried on, multiplied by the number of trucks used in transport.

Input

The first line of input contains an integer N that determines the number of test cases (or days of working in the desert). Each test case is composed by two lines. The first line contain three integer numbers: nPainels (4 ≤ nPainels ≤ 100), trucks (1 ≤ trucks ≤ 10) and freight (1 ≤ freight ≤ 50) separated by a blank space, indicating respectively the number of panels to be transported, the number of trucks used to this transport and the freight value for each kg transported. The following line contains the weight (1 ≤ weight ≤ 1000) of each panel, separated by a blank space.

Output

For each test case, your program must print a line, informing the weight of the most loaded truck, followed by a blank space and the total value of freight value for a day worked.

Sample Input Sample Output

4
5 2 1
20 25 30 40 45
9 3 10
20 10 30 40 50 60 90 80 70
10 4 5
65 10 15 14 70 95 65 25 26 35
4 1 1
23 45 77 90

85 $170
150 $4500
151 $3020
235 $235