[Solution] Buying Sweets solution codechef

Buying Sweets solution codechef – There are NN sweets in the store. The cost of the ithith sweet is AiAi rupees. Chef is a regular customer, so after buying the ithith sweet, he gets a cashback of BiBi rupees.

[Solution] Buying Sweets solution codechef

Chef has RR rupees. He is fond of all the sweets, so he wants you to calculate the maximum number of sweets he can buy. Note that he can buy the same type of sweet multiple times, as long as he has the money to do so.

Input Format

  • The first line of input will contain TT, the number of test cases.
  • Each test case consists of three lines of input.
  • The first line of each test case contains two space-separated integers NN and RR — the number of sweets in the shop and the amount of money Chef has.
  • The second line of each test case contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.
  • The third line of each test case contains NN space-separated integers B1,B2,,BNB1,B2,…,BN.

Output Format

For each query, print on a new line the maximum number of sweets Chef can buy.

[Solution] Buying Sweets solution codechef

  • 1T21051≤T≤2⋅105
  • 1N21051≤N≤2⋅105
  • 1Bi<Ai1091≤Bi<Ai≤109
  • 1R1091≤R≤109
  • It is guaranteed that the sum of NN over all test cases does not exceed 21052⋅105

Sample Input 1 

3 3
2 3 4
1 1 1
2 4
5 4
1 2
4 10
4 4 5 5
1 2 4 2

Sample Output 1 


Buying Sweets solution codechef Explanation

Test case 11: Chef buys the first sweet, which costs 22 rupees and has a cashback of 11 rupee. He now has 32+1=23−2+1=2 rupees remaining. He once again buys the first sweet, which leaves him with 11 rupee, at which point no more sweets can be bought.

Test case 22: Chef buys the second sweet once.

For Solution

Click here

Leave a Comment