beforethestorm

Total War: Three Kingdoms
The Secret of the Great King
 
Chapter 1: Before The Storm
 
Each army need to be picked and trained very carefully.
It's the key value of the greate Soldier as a Leader and the future king.
As the resident have a special type of ability, the leader divide them in to K type of army.
The more army the more power.
The more they train, the more they get strong.
But the capability of a kingdom is limited. They only have M food (don't stack after each month, you can say that they only accept the total food this kingdom spend for the army is M).
The time before the war also short, they only have N month.
 
As those information, the wise leader connect those information and start to prepare
He know the capability of the kingdom as M.
The time before the war is N month (N<=10).
He have K type of army with an estimate information (K<=10).
Cost per month, the base power can be train at first month, the capability of increment in power each month later.
 
Help him to find out how much power he can brought  out from this situation.
 
Input:
10 //number of testcase
1000 3 // M N (testcase1)
5 // K (in next K line: Cost, BasePower and Increment each month are given)
500 150 10
500 200 0
500 170 10
500 140 15
500 190 1
1000 3 // Start of testcase 2
5
500 150 10
500 200 0
500 170 15
500 140 15
500 190 1
 
Output:
#1 392
#2 400
 
Explain
1st  Testcase:
M = 1000
N = 3
Cost	Power	Increment
500	150	10
500	200	0
500	170	10
500	140	15
500	190	1
Step:
Month	1st pick	2nd pick	3rd pick	Total
1	190	 	 	190
2	191	200	 	391
3	192	200	x	392
 
In first month, we train the army 5 (with gave 190 power after first training)
In second month, the power of 5th army become 191. We start to train the 2nd army and get 200 as the base power.
In the third month, we can’t train other army because we out of food. So the 1st pick army get stronger by 1 and in final we have 392 as the biggest power
 
Same as testcase 2, we pick army 3 (500 170 15) and then pick the army2  (500 200 0)
After 3 month we get total 400 power.

Full test case will be upload later

7
1000 3
5
500 150 10
500 200 0
500 170 10
500 140 15
500 190 1
1000 3
5
500 150 10
500 200 0
500 170 15
500 140 15
500 190 1
2000 3
5
100 200 20
150 150 30
200 200 15
300 300 5
1000 500 0
1000 8
5
100 200 20
150 150 30
200 200 15
300 300 5
1000 500 0
2000 8
5
100 200 20
150 150 30
200 200 15
300 300 5
1000 500 0
2000 8
10
100 200 20
150 150 30
200 200 15
300 300 5
1000 500 0
100 200 20
150 150 30
200 200 15
300 300 5
1000 500 0
2000 10
10
100 200 20
150 150 30
200 200 15
300 300 5
1000 500 0
100 200 20
150 150 30
200 200 15
300 300 5
1000 500 0

****
#1 392
#2 400
#3 1045
#4 1275
#5 1775
#6 2350
#7 2630