DBALLZ - Help the Heroes


Our heroes Vegeta and Goku are fighting against the evil MajinBuu. Goku planned to hit MajinBuu with the spirit-bomb which is a bomb that contains pure energy such that no evil hearted enemy can withstand the impact. Unfortunately Goku needs some time to collect pure energy from all the living things in the universe. So Vegeta is going to distract MajinBuu so that Goku will get his time to concentrate on getting pure energy from the whole universe. Let's call this as the "Distraction time".

MajinBuu has this ability to regain its shape once it has been blast into pieces. Vegeta is ready to sacrifice his life by fighting with MajinBuu. You are provided with the total energy of Vegeta, the list of energy blasts that Vegeta can perform in his life time and list of numbers which represents the 'time' to regain MajinBuu's shape corresponding to the energy blast of Vegeta. This list of 'time' is the duration of distraction in which Goku can gather energy from the whole universe. It's better if it's more. Your task is to find out the maximum distraction time.

Input

The first line contains the total number of test cases T ≤ 50.

The second line contains E < 106 (energy of Vegeta) and L ≤ 1000 (length of the energy list.)

Following lines contains two lists of integers, first, the energy list and then the corresponding time span list.

Output

Print the maximum time of distraction gained for each test cases.

Example

Input:
1
100 4
20 30 40 60
2 4 5 6

Output:
13

Note

Vegeta can't fight once he has lost his whole energy. That is, his energy can't become less than zero. Unless the value of the blast is greater than Vegeta's energy, he can use a blast more than once.


hide comments
Akhilesh Anandh: 2014-11-14 09:15:01

Constraints on values of time?

Edit:
Got accepted assuming that total distraction time fits in 32 bit signed integer.

Last edit: 2014-11-13 20:55:58
Sankaranarayanan G: 2014-11-14 09:15:01

No, he can't. It is meaningless if he could use a blast that is greater than his own energy.

The way of choosing the blasts is the task here. If Vegeta hits with 30,30 and then 40, you will get a distraction time of 13s.

Last edit: 2014-11-13 16:45:07
shravan: 2014-11-14 09:15:01

Can Vegenta blast an energy with value K even if Vegenta's energy reserve is less than K?

Can you explain the output 13 against the test case


Added by:mombassa
Date:2014-11-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CSAU Online Programming Contest 2014