**Problem Statement:**

There is an array "cost" of length n, cost[i] is the cost of i'th robot and an array "A" of length n, A[i] is the number written on the i'th robot, you are also given an integer K which is the amount you have. You can buy a robot only if cost of that robot is less than or equal to the remaining amount you have(obviously).

Suppose you buy x robots with indices i1, i2, i3 ... ix then you will get one gift card for each i such that A[i] >= x (i belongs to indices of robots you purchased). Calculate the maximum number of gift cards you can get.

**Constraints**

1<= n <= 100

1<= K <= 1e9

1<= cost[i] <= 1e4

1<= A[i] <= n

**Sample Input**

5 300 <-- (n, K)

4 5 4 3 2 <-- (cost)

120 150 80 90 100 <-- (A)

**Sample Output**

2

**Explanation**

Buy robots with indices 3,4,5 cost 270(<=300) and you will get 2 gift cards for robots 4 and 5

I was thinking of some knapsack type approach but was not able to get a solution. You can comment your solution or post a link to a similar problem with solution, thanks.

Till I am able to think you can do it with binary search

Ist observation : if you buy k robots and gift you get let y (y < k) then it is optimal to just buy y robots so that you get also y gift

Ex -> let you buy i1 i2 i3 i4 i5 , corresponding A[i] value 6 5 1 2 2 it is optimal to buy 6 5 only since these are contributing

Now Our goal to maximize the y(robot you buy and all contributing to the answer)

Binary Search over y (1...n) for fix y you can club the elements that has A[i] >= y then you pick smallest y elements among them and check their sum <= k or not

I think this works fine , If not plz let me know