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 < 10^6 (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.


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

hide comments
2017-09-22 13:23:17
Unbounded knapsack it is.
2017-05-30 16:57:11
is this problem unbounded knapsack?
2017-05-24 03:18:16 Kirito
simple dp
2017-01-26 12:55:20
dont use long long use only int that cause me 5 tle
2017-01-21 17:24:24
My 100th .....Don't use spoj toolkit ...wrong for this question
2016-10-09 16:44:17
AC in one go..:) Knapsack with duplicate items..:)
2016-10-09 07:35:03 subhasmita sahoo
Bottom Up.O(L*E).
2016-09-12 20:44:39
easy do this for points:)
Edit-> Toolkit gives wrong answer don't look there for testcases

Last edit: 2016-09-12 20:46:22
2016-09-04 08:15:10 Shubhojeet Chakraborty
O(t*l*e) Top down+32 bit integer passes in time.
2016-08-07 08:47:00
Straightforward ! :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.