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.

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Download More RAM

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputDid 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.

Example

Input

4 3 10 20 30 10 9 100 10 5 1 1 1 5 1 1 1 1 1 1 1 5 1 2 2 2 2 2 100 100 100 100 100 5 8 128 64 32 16 8 128 64 32 16 8

Output

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-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/20/2022 04:00:50 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|