Maximum Shares

You have recently read the biography of Warren Buffet and are very excited to start your investing journey. So, you have decided to buy shares of a certain company. Now, you have an initial capital of Rs ‘K’. You know the prices of the particular stock for the next ‘N’ days. On an ith day, you can buy up to i shares. To maximize the profit you want to buy a maximum number of shares, so find the maximum number of shares you can buy if you buy optimally.

Example:-

Let, 
K = 45
N =3
PRICES = [10, 7, 19]
Answer:- 4
The answer should be 4 because you can purchase 1 stock on day 1,2 stocks on day 2 and 1 stock on day 3. Hence, total amount spent is 10*1 + 7*2 + 19*1 = 43 and number of stocks purchased is 4.

Input Format :

The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.

The first line of each test case contains an integer ‘K’ denoting the initial capital you have.

The second line of each test case contains an integer ‘N’ denoting the number of days for which you know the price for the particular stock.

The third line contains ‘N’ integers of the array ‘PRICES’ denoting the price of the stock on an ith day.

Output Format :

For each test case, print an integer denoting the maximum amount of stocks you can buy if you act in an optimal manner.

The output of each test case should be printed in a separate line.

Note :

You are not required to print anything, it has already been taken care of. Just implement the function.    

Constraints :

1 <= T <= 5
 1 <= K <= 10^9
1 <= N <= 10^5
1 <= PRICES[i] <= 10^9

Time Limit = 1 sec