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
2016-07-20 10:49:09 shreynik kumar
bottom-up dp + use global array....O(t*l*e)passes
2016-07-18 10:38:02
Simple bottom-up dp. :)
2016-05-31 13:27:03
Bottom up gave TLE where as memoization gave AC . Also ios::sync_with_stdio(false) gave TLE while scanf gave AC.
Strange.
BTW 100th user to solve this

Last edit: 2016-05-31 13:28:42
2016-01-22 23:05:20 Arjav
exact same code in c++14 gives tle but get ac in c++4.3.2......
very strict tle!!! for solution of O(t*l*e)...

Last edit: 2016-01-22 23:14:52
2016-01-01 20:21:20 kejriwal
anyone who did better better than O(t*e*l).. can you give some hint..O(t*e*l) also passed though lol xD !!
2015-10-07 14:51:24 Rishav Goyal
easy
2015-08-22 10:36:42 SRC
O(T*L*E) doesn't pass when I use unbounded Knapsack.Getting a TLE. Please help.
2015-03-10 18:58:16 aristofanis
Strange! O(T*L*E) didn't get TLE...
2014-11-15 06:08:05 Jacob Plachta
It seems that the data is much smaller than suggested by the given constraints - O(T*E*L) passes.
2014-11-14 14:28:47 ivar.raknahs
can he have same energy with different time span , i mean this.
energy=> 20 30 40 40 50
time=> 2 3 4 4 5
?
and values in energy list must be >0 ?

Last edit: 2014-11-14 15:21:28
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.