Minimum Payment
Problem
Mr. Seth decorates his shop with Paintings. He then planned to buy exactly K ones. He can buy them from a nearby shop and there are 2 types of Paintings available. The shop has a rule for customers that If anyone buys K paintings of type 1 then the customer must pay L * K2 and L1 *M2 if you buy M paintings of type 2. Please help Mr. Seth to buy exactly K paintings at a minimum amount of payment.
Input Format
- The first line contains an integer T denoting the number of test cases.
- Each test case is described in a single line containing three space-separated integers K, L, L1.
Output Format
For each test case, print a single line containing the answer.
Constraints
- 1 ≤ T ≤ 105
- 1 ≤ K, L, L1 ≤ 105
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
Query 1: we have to buy exactly 5 paintings. There are six possible options:
- Buy 0 painting of first type, 5 paintings of second type. The cost is: 1×02+2×52=50.
- Buy 1 painting of first type, 4 paintings of second type. The cost is: 1×12+2×42=33.
- Buy 2 painting of first type, 3 paintings of second type. The cost is: 1×22+2×32=22.
- Buy 3 painting of first type, 2 paintings of second type. The cost is: 1×32+2×22=17.
- Buy 4 painting of first type, 1 painting of second type. The cost is: 1×42+2×12=18.
- Buy 5 painting of first type, 0 painting of second type. The cost is: 1×52+2×02=25.
So, the optimal cost is 17.
