Problem title
Difficulty
Avg time to solve

Subarray Sums I
Moderate
15 mins
Split the String
Easy
--
Morty and his array
Hard
--
Get Path using BFS
Easy
25 mins
Design Browser History
Moderate
25 mins
Maximum Shares
Easy
30 mins
Complete Sum
Easy
15 mins
Sentence Sort
Easy
--
Postorder Traversal
Easy
--
Minimum Swaps To Make Identical Array
Moderate
-- 7

# Maximum Shares

Difficulty: EASY
Avg. time to solve
30 min
Success Rate
70%

Problem Statement

#### 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]
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
``````
##### Sample Input 1 :
``````2
6
3
1 2 3
1
2
3 10
``````
##### Sample Output 1 :
``````3
0
``````
##### Explanation for Sample Output 1 :
``````In the first test case, the answer should be 3 because you can buy 1 share on the first day and 2 shares on the second day.
In the second test case, the answer should be 0 because you can’t buy any number of shares on any day.
``````
##### Sample Input 2 :
``````1
100
3
7 10 4
``````
##### Sample Output 2 :
``````6
``````   Console