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

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

hide comments
2022-02-21 18:30:47
If for python 3 you occasionally get tle use Python 2 (PyPy 2.7.13) , syntax is almost similar.
Although for this question Python 3 works just fine, maybe you are doing something wrong.
As a suggestion I would say for each mid time in outer search space, use AP quadratic formula to calculate the potential number of parathas don't use 2 nested loops even though in constraints it says L <= 50.
For python 2 take care of float division.

Last edit: 2022-02-21 18:34:06
2021-12-24 14:45:17
The reason answer for first use case P = 10, R[] = [1,2,3,4], Ans = 12 is:
1. Let's take answer as 10 so:
* first will make (1+2+3+4 = 10min) i.e. 4Prata
* Second will make (2 + 4 = 6min) i.e. 2Prata. Note we cannot take 3rd prata time as total time will become 2 + 4 + 6 = 12min in that case
* Third will make (3 + 6 = 9min) i.e. 2 Prata
* Fourth will make (4min) i.e. 1Prata
So if time = 10 then Prata = 4 + 2 + 2 + 1 = 9 Prata
And similarly to make 10Prata min time will be 12min
2021-10-25 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
2021-09-11 17:39:00
why we need 12 min in 1st example?
we can do it in 10
1 will cook 4 in 10 min
2 will cook 2 in 6 min
3 will cook 2 in 9 min
4s will cook 1 each in 4 min
4+2+2+1+1 = 10
Ohh understod first integer indicates the no of cooks so here 4 in not the rank of cook rather it is no of cook



Last edit: 2021-09-11 17:44:40
2021-09-05 09:52:22
great question
2021-08-14 13:23:18
what will be the max required time in worst case...???




Last edit: 2021-08-14 13:23:44
2021-07-20 18:54:56
why we need 12 min in 1st example?
we can do it in 10
1 will cook 4 in 10 min
2 will cook 2 in 6 min
3 will cook 2 in 9 min
4s will cook 1 each in 4 min
4+2+2+1+1 = 10


2021-07-14 16:28:18
why tle in python? does this platform doesn't considers slow languages?
2021-06-30 08:04:47
Easy peasy lemon squeezzzy !!. Very good question on binary search.
2021-06-19 07:22:16
accepted in second Go!!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.