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
2023-12-25 07:35:29
Solution :
1.dry run test case on notebook and see how we get answer
2.make a bool fxn which shows can "time" give us parathas>=P
3.calculate min and max time possible take hints from solution(sum of n terms of ap).
4.iterate time(search space) by Linear search 1st then optimize it by Binary Search .
Try to come up with the code by yourself.

Here is the Code:
<snip>
[Simes]: no thanks

Last edit: 2023-12-27 09:48:11
2023-12-23 16:30:54
What is faster. Heap approach or binary search?
2023-07-15 08:45:23
guys my solution works for the example test cases given above. But somehow after/at test 2, it gives a wrong answer. I'm not able to get the problem :(
2023-07-13 06:41:01
I solved it using min_heap
<snip>
[Simes]: No thanks, this is a site for people who want to write their own code

Last edit: 2023-07-13 09:06:44
2023-07-09 13:44:45
I used double BS.. wbu guys?
2023-07-07 14:16:05
<snip>
[Simes]: read the footer, don't post code here.

Last edit: 2023-07-07 16:42:58
2023-05-26 16:10:06
<snip>

Last edit: 2023-05-26 16:39:39
2023-02-22 09:53:20
Took 2hrs but finally solved!
2022-06-28 20:01:11
Done in 1st go. Nice and Conceptual Problem.
Hint 1 : understand the problem correctly
Hint 2 : estimate the largest time required correctly
2022-03-15 20:55:00
Hint 1: sum of 1st n natural number is n*(n + 1) / 2
Hint 2(in case of TLE in binary Search): high = maximum time to get p paratas not INT_MAX
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.