ZOJ Problem Set - 2875
The great Lucky Luke and his smart horse Jolly Jumper are again caught the four evil Dalton brothers and sent them to the prison. As a reward, the governor of the province in which the Daltons had been caught, gave a collection of gold stones to Luke. At first, Luke became very happy for obtaining such a treasure, but he remembered he had a limited space to carry these stones. In fact, he can just count on the kyack on the back of Jolly which consists of two bags with volume V on either side of Jolly��s packsaddle. As a result, he cannot carry all the stones and must take just some of them.
He thought, "At least, I can use as much space as possible in the Jolly��s kyack by taking a portion of some of the stones with myself." But Unlucky Luke found that all smiths, instead of their wage for cutting the portion of a stone that he wants, will take the left portion of the stone (for example, if Luke gives the smith one stone and asks him to cut and give him 20% of it, the smith will take the remaining 80% as his wage). What an unfair deal! They know Luke is rich now and will not change their mind! Now, Luke wants to select a portion of each stone in a way that he could place them in two bags in his kyack without exceeding their volume and the selected stones have the maximum total value. Unfortunately, Luke that fires a gun faster than his shadow (see the picture below for the proof of this claim!) can not solve this problem and needs your help! It should be noted that a portion with P% of a stone volume has P% of its value.
Input begins with a number T showing the number of test cases and then, T test cases follow. Each test case begins with a line containing an integer 1 <= n <= 100 and a positive real number V <= 5000 representing the number of stones and volume of each bag respectively. After that, a line containing n positive integers less than or equal to 100 will come where the i-th number shows the volume of i-th gold stone. Then, a line containing n positive real numbers will come where the ith number shows the value of ith gold stone.
For each test case, your program must output the maximum total value of stones which can be carried by Luke rounded to four digits after the decimal point.
Author: Babak Behsaz
Source: AUT Contest 1