Your task is to collect apples from various farms. You can move sequentially from your house to the first farm, the first farm to the second farm, from the second farm to the third farm, and so on.

This direction of movement is as follows:

House $- > 1^{st} \space farm -> 2^{nd} -> 3^{rd} -> 4^{th} -> 5^{th}.. ->N^{th}$ and so on

There are $N$ farms in a line. Moving from one farm to the next farm consumes a single unit of your energy. Therefore, you may have to refill your energy. You can ask the owner of a farm to provide you milk so that you can gain some energy. The farm owner agrees to provide you milk only on one condition that you cannot take apples from that farm.

At each farm, you are either allowed to drink milk or take apples. Each farm contains different amount of apples and milk. Therefore, from each farm, you are allowed to take only either the entire amount of milk or apples. From each farm, you cannot take both apples and milk or none of them.

Your task is to determine the maximum number of apples that you can collect always having non-negative energy.

Note: Initially, you are at your house. It takes one unit of energy to move to the first farm.

Input format

• First line: A single integer $t$ denoting the number of test cases in a single test file
• Second line: $N$ and $P$ denoting the number of farms and your initial energy level
• Third line: $N$ space-separated integers, where the $i^{th}$ integer is $Milk[i]$ and denotes the amount of energy that you can gain by drinking milk from the $i^{th}$ farm
• Fourth line: $N$ space-separated integers, where the $i^{th}$ integer is $Apples[i]$ and denotes the number of apples that you can collect from the $i^{th}$ farm if you do not drink milk from that farm

Constraints

$1 \le t \le 100$

$1 \le N \le 1000$

$0 \le P \le 10^{18}$

$0 \le Milk[i] \le 1000$

$0 \le Apples[i] \le 1000$