Problem - 1629A - Codeforces

Maybe your like

Enter | Register

Home
Top
Catalog
Contests
Gym
Problemset
Groups
Rating
Edu
API
Calendar
Help

Codeforces Round 767 (Div. 2)
Finished

→ Virtual participation Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests. If you've seen these problems, a virtual contest is not for you - solve these problems in the archive. If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive. Never use someone else's code, read the tutorials or communicate with other person during a virtual contest. → Problem tags brute force greedy sortings *800 No tag edit access → Contest materials

Announcement (en)
Tutorial (en)

Problems
Submit
Status
Standings
Custom test

The problem statement has recently been changed. View the changes. × A. Download More RAMtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Did you know you can download more RAM? There is a shop with $$$n$$$ different pieces of software that increase your RAM. The $$$i$$$-th RAM increasing software takes $$$a_i$$$ GB of memory to run (temporarily, once the program is done running, you get the RAM back), and gives you an additional $$$b_i$$$ GB of RAM (permanently). Each software can only be used once. Your PC currently has $$$k$$$ GB of RAM.

Note that you can't use a RAM-increasing software if it takes more GB of RAM to use than what you currently have.

Since RAM is the most important thing in the world, you wonder, what is the maximum possible amount of RAM achievable?

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains the integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100$$$, $$$1 \le k \le 1000$$$). Then two lines follow, each containing $$$n$$$ integers describing the arrays $$$a$$$ and $$$b$$$ ($$$1 \le a_i, b_i \le 1000$$$).

Output

For each test case, output a single line containing the largest amount of RAM you can achieve.

ExampleInput 43 1020 30 109 100 105 11 1 5 1 11 1 1 1 15 12 2 2 2 2100 100 100 100 1005 8128 64 32 16 8128 64 32 16 8Output 29 6 1 256 Note

In the first test case, you only have enough RAM to run the third software initially, but that increases your RAM to $$$20$$$ GB, which allows you to use the first software, increasing your RAM to $$$29$$$ GB. The only software left needs $$$30$$$ GB of RAM, so you have to stop here.

In the second test case, you can use the first, second, fourth and fifth software that need only $$$1$$$ GB of RAM per software to run to increase your RAM to $$$5$$$ GB, and then use the last remaining one to increase your RAM to $$$6$$$ GB.

In the third test case, all the software need more than $$$1$$$ GB of RAM to run, so the amount of RAM you have stays at $$$1$$$ GB.

Codeforces (c) Copyright 2010-2025 Mike Mirzayanov The only programming contests Web 2.0 platform Server time: Dec/26/2025 07:58:00 (l1). Desktop version, switch to mobile version. Privacy Policy | Terms and Conditions Supported by TON