PRATA  Roti Prata
IEEE is having its AGM next week and the president wants to serve cheese prata after the meeting. The subcommittee members are asked to go to food connection and get P (P<=1000) pratas packed for the function. The stall has L cooks (L<=50) and each cook has a rank R (1<=R<=8). A cook with a rank R can cook 1 prata in the first R minutes 1 more prata in the next 2R minutes, 1 more prata in 3R minutes and so on(he can only cook a complete prata) ( For example if a cook is ranked 2.. he will cook one prata in 2 minutes one more prata in the next 4 mins an one more in the next 6 minutes hence in total 12 minutes he cooks 3 pratas in 13 minutes also he can cook only 3 pratas as he does not have enough time for the 4th prata). The webmaster wants to know the minimum time to get the order done. Please write a program to help him out.
Input
The first line tells the number of test cases. Each test case consist of 2 lines. In the first line of the test case we have P the number of prata ordered. In the next line the first integer denotes the number of cooks L and L integers follow in the same line each denoting the rank of a cook.
Output
Print an integer which tells the number of minutes needed to get the order done.
Example
Input:
3
10
4 1 2 3 4
8
1 1
8
8 1 1 1 1 1 1 1 1
Output:
12
36
1
hide comments
shubhamphpefy:
20221216 20:20:01
Last edit: 20221216 20:20:44 

jeet_manojit:
20220914 06:05:25
Last edit: 20220914 08:07:04 

ayush_7901:
20220628 20:01:11
Done in 1st go. Nice and Conceptual Problem.


piyushkrs:
20220315 20:55:00
Hint 1: sum of 1st n natural number is n*(n + 1) / 2


tejas07_psk:
20220221 18:30:47
If for python 3 you occasionally get tle use Python 2 (PyPy 2.7.13) , syntax is almost similar.


ankit_mzp:
20211224 14:45:17
The reason answer for first use case P = 10, R[] = [1,2,3,4], Ans = 12 is:


avishjain2002:
20211025 18:15:31
beatrock why are you taking the rank 4 cook two times the starting four means that there are four cooks see input 

beatrock:
20210911 17:39:00
why we need 12 min in 1st example?


sj_2330:
20210905 09:52:22
great question 

bappa_10:
20210814 13:23:18
what will be the max required time in worst case...???

Added by:  Saransh Bansal 
Date:  20110514 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem NTU IEEE codejam 2011 