403793: GYM101306 F Wifi Trees

Martians have discovered the answer to life, the universe, and everything. No, not 42. Wifi trees!

Martian lungs are adapted to survive without Oxygen for a looong time, but that time is about to end.

The Martians have managed to plant n Wifi trees, each additional tree supplying them with x Mbps of Wifi. However, each Martian requires one Oxygen tree in order to survive.

The government does not want to spend money on planting new trees, but it can convert some Wifi trees to Oxygen trees. Being utilitarian by nature, it wants to maximise total happiness.

Each Martian will have 1 happiness for each Mbps of Wifi he gets. However, dead Martians cannot be happy. The total happiness is the sum of happiness of each of the Martians.

Formally, happiness of some Martian i is defined as follows: H_i = a_i·t·x.

a_i is 1 if that Martian is alive, 0 otherwise. t is the number of Wifi trees.

Total happiness is therefore .

What is the minimum number of trees the government should convert to maximise total happiness?

The first line of the input contains an integer T, the number of test cases (1 ≤ T ≤ 5).

Each of the next T input represents a test case, and consists of 3 space-separated integers n, m,  and x (1 ≤ n, m ≤ 10⁹; 1 ≤ x ≤ 5), the number of Wifi trees, the number of Martians, and the additional bitrate provided by each Wifi tree, respectively.

Print T lines of output, one for each test case. On each line print two space-separated integers.

The first integer is the minimum number of Wifi trees that should be converted to Oxygen trees.

The second integer is the maximum happiness achieved.

1
5 3 2

2 12

2
42 83 1
1000000000 1000000000 5

21 441
500000000 1250000000000000000

To avoid overflows, use 'unsigned long long' or 'long long' in C++, and 'long' in Java, instead of 'int'