Ajay is a very hard working man but he doesn't care about his health, so he has become very weak now.He went to the doctor for a health checkup and the doctor suggested him to eat as many eggs as possible.So, he goes to the shops daily and gets eggs for himself.
Ajay is at his home initially, and to move to the first shop it shall cost him one chocolate. He goes serially from his home to first shop, from first to second and third and so on.
So he will move like this: Home --> 1st shop --> 2nd --> 3rd --> 4th ... --> Pth and so on.
There are P shops in a line. Travelling from one shop to the next shop cost one chocolate of his current available chocolates. So he need to put some chocolates to his chocolate box sometimes. He can request a shop owner to offer him some chocolates. The shop owner admits to give him chocolates but with a condition that he can't take eggs from that shop.
So, at each shop, Ajay has one choice either to take chocolates or eggs from the shop. Each shop has different amount of eggs and chocolates. So, from each shop, Ajay is allowed to take only either the entire amount of chocolate or the entire amount of eggs and not none or both.
By following this rule, what is the maximum number of eggs Ajay can collect, always having number of chocolates greater than or equal to zero?
Initially Ajay is at his home, and to move to the first shop it shall cost him one chocolate.
Input :
First line of each test file contains a single integer T denoting number of test case. Each test case contains three lines.
First line contains two space separated integers P and E denoting total number of shops and number of chocolates Ajay initially has.
Second line contains P space separated integers, where the ith integer is Chocolates[i] and denotes the total number of chocolates Ajay can gain by taking chocolates from the ith shop.
Third line contains P space separated integers, where the ith integer is Eggs[i] and denotes the total number of eggs Ajay can gain by taking eggs from the ith shop if he will not take chocolates from that shop.
Output : For each test case answer in new line maximum number of eggs Ajay can collect.
Constraints :
1 ≤ T ≤ 100
1 ≤ P ≤ 1000
0 ≤ E ≤ 1018
0 ≤ Chocolates[i] ≤ 1000
0 ≤ Eggs[i] ≤ 1000
In first test case of sample , there are 3 shops in a line, and Ajay has 2 chocolates initially. He will first go from his home to first shop. After this,
Chocolates: 1, Eggs: 0
He will then take all eggs available in the first shop, and then go to second shop
Chocolates :0, Eggs: 100
He will then take all the chocolates available in the second shop and go to third shop.
Chocolates: 1 , Eggs: 100
He will then take all the eggs available in the last shop and finish his journey.
Chocolates: 0 ,Eggs: 200
This is the maximum number of eggs Ajay can collect.
