CDGLF2 - AAP Volunteers

AAP Volunteers

 

After AAP’s massive victory in Delhi Assembly Elections 2015, AAP Volunteers have decided to clean the streets of delhi by collecting all the pamplets, caps, campaign material lying here and there and then putting them in the dustbin. There are ‘n’ different sites each having 1 bag full of these used materials and each bag has a certain value ‘Vi’ associated with it. A volunteer can travel only a certain distance ‘W’ at max. Suppose, site ‘i’ has a bag whose value is ‘Vi’ and the distance of that site from the dustbin is ‘Di’ , then the volunteer has to travel 2*Di distance (from dustbin to that site and from that site to the dustbin) and is thus able to earn ‘Vi’ points. Your task is to find out the maximum number of points that can be earned by the volunteer under the constraints that he can carry only 1 bag at a time and maximum distance that can be travelled by him is ‘W’ (in total).

 

Note: There is only one dustbin.

 

Input

First line of input consists of ‘T’ denoting number of test cases .First line of each test case consists of ‘n’- number of sites and ‘W’-maximum distance that can be travelled by the volunteer in total. Second line consists of ‘n’ numbers( D1,D2,...,Dn) where ‘Di’ denotes the distance of that site from the dustbin and third line consists of ‘n’ numbers( V1,V2,...Vn) where ‘Vi’ denotes the value associated with the bag at the ‘i’th site.

 

Output

Print the desired value on a separate line for each test case.

 

Constraints

1<=T<=50

1<=n<=10^3

1<=W<=10^3

1<=Vi<=10^8

1<=Di<=10^8

 

Sample Input

1

3 10

3 4 1

100 200 300

 

Sample Output

500


 


Added by:CSI
Date:2015-02-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY

hide comments
2015-02-27 04:07:33 Mitch Schwartz
I'm not aware of any input irregularities. My code doesn't use any defensive input reading techniques.

Edit: Good catch on W=0.

Last edit: 2015-02-27 20:27:02
2015-02-27 03:47:59 (Tjandra Satria Gunawan)(曾毅昆)
Problem with python although it run perfectly on ideone and my computer:
- Read t cases = NZEC
- Read till EOF "try:get input; except:break" = WA
- Read with this "try:get input; except continue" = TLE
I'll try with C
EDIT: my bad, I forgot case when W=1 in python, sorry :-/
EDIT2: There are a case where W=0 in input, problem description is incorrect

Last edit: 2015-02-27 05:29:32
2015-02-14 02:32:44 Mitch Schwartz
(Edited to remove unnecessary info) I hid the problem for brief time period because of questionable time limit, but made it visible again after doing some experiments. Possibly 2s would be better, since current time limit of 1s is a bit tight for slower languages.

Another edit: Found another optimisation; I think the time limit is ok.

Last edit: 2015-02-19 00:23:18
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.