Solve More Problems | codechef | Starters 78

Problem

Chef came across a new online judge that has N problems, and decided that he wants to solve them.

Chef takes Ai​ consecutive minutes to solve the i-th problem, and will take a break of Bi​ minutes immediately after solving it.
That is, Chef will solve a problem, then take a break. Solve another problem, then take another break, and so on.

Chef has K minutes of free time. If he chooses the problems and their order optimally, what is the maximum number of problems he can solve in this time?

Note that a problem is considered solved if Chef finishes solving it by the K-th minute, even if the break time of the last problem extends past minute K. See the sample tests below for an example.

Input Format

  • The first line of input will contain a single integer T, denoting 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 N and K — the number of problems in the online judge and Chef’s free time, respectively.
    • The second line of each test case contains space-separated integers — the values 1,2,…,A1​,A2​,…,AN​.
    • The third line of each test case contains N space-separated integers — the values 1,2,…,B1​,B2​,…,BN​.

Output Format

For each test case, output on a new line the maximum number of problems that Chef can solve within K minutes.

Constraints

  • 1≤T≤2⋅104
  • 1≤N≤2⋅105
  • 1≤K≤108
  • 1≤Ai​≤108
  • 0≤Bi​≤108
  • The sum of N over all test cases won’t exceed 2⋅1052⋅105.

Sample 1:

Input

Output

4
3 10
3 4 5
2 4 2
3 8
3 4 5
2 4 2
5 20
23 54 124 54 83
2 9 5 2 10
5 20
4 7 12 34 13
30 4 3 0 9
2
1
0
2

Explanation:

Test case 11: Chef can solve the first problem followed by the second problem.

  • 33 minutes for the first problem
  • 22 minutes of break time after solving it, for a total of 55 minutes
  • 55 minutes for the third problem, for a total of 1010 minutes
  • There’s one minute of break time left which goes beyond 1010 minutes, but that’s ok: Chef finished solving 22 problems within 1010 minutes.

Test case 22: The same times as the first sample, but with �=8K=8. Now, Chef can solve any one problem, but cannot solve a second one no matter what.

Test case 33: Chef can’t solve anything within 2020 minutes.

Test case 44: Chef can solve the third problem followed by the first problem.

Click on the below image to get solution link:

solution

Leave a Reply

Your email address will not be published. Required fields are marked *

मिर्जापुर 3 के बोनस एपिसोड में मुन्ना भैया की वापसी? आपकी साँसे थम जाएंगी! ये है आपके PAN CARD की एक्सपायरी डेट, कहीं छूट तो नहीं गई? यकीन नहीं मानोगे! ये 9 जगहें हैं UP में जो ताजमहल को भी फीका कर देंगी! मेरठ: इतिहास, धर्म और खूबसूरती का संगम! घूमने के लिए ये हैं बेहतरीन जगहें रोज आंवला खाने के 10 धांसू फायदे जो आपको कर देंगे हेल्दी और फिट! Anjali Arora to play Maa Sita: रामायण फिल्म में सीता का रोल निभाएंगी अंजली अरोड़ा, तैयारियों में लगी?