Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Nilkhet

By curly_braces · Limits 1s, 512 MB

You’re planning to start a library for the next nn days, where you will rent books to students. Each day you will serve a single student. The students will come in the morning take a book and return it before evening. Your shelves in the library can hold at most mm books at a time. To stock the shelves, you will go to the local book market called Nilkhet. At Nilkhet kk types of books are available numbered from 11 to kk. Each book has a purchasing price pip_i and a return price rir_i. That means you have to pay pip_i amount of money to buy the book but after that, if you want to return it the shop will give you rir_i money back. It is guaranteed that for all the books pi>rip_i>r_i. Each night you go to Nilkhet, return some(zero or more) books that you previously bought and after that buy some(zero or more) books to stock your library. Remember your shelves can only keep mm books at a time. So before buying books you may need to return some to make empty spaces for the books. Initially, all shelves are empty.

You want to serve all the students who will visit your shop in the next nn days. The student can only borrow a book if you have it in stock already. Even though charity is the main objective of your library, you don’t want to lose any money in the process. So you will charge students rent for each book. Let ss be a real number that represents the renting rate, meaning if a student wants to borrow a book then they have to pay ss% of the purchasing price of that book as rent.

Given the type of books that students will borrow sequentially, your task is to find minimum real number ss, that if students pay ss% of the purchasing price as rent and you buy and return books optimally then you’ll not lose any money after serving all the students.

Formally you’ll not lose money if and only if, the Total cost of buying books \geq Rent collected ++ Money gained from returning books.

Input

Input starts with an integer T(1T100)T( 1 \leq T \leq 100) number of test cases.

Each test case starts with 3 integers n,m,k(1n,m,k100)n,m, k(1 \leq n,m, k \leq 100), the number of days, the capacity of you library and the number of book types.

The next line contains kk integers p1,p2,p3,,pk(1pi109)p_1,p_2,p_3, \dots ,p_k (1\leq p_i \leq 10^9), the purchasing price of books of ithi’th type.

The next line contains kk integers r1,r2,r3,,rk(1ri<pi)r_1,r_2,r_3, \dots ,r_k (1\leq r_i < p_i), the returning price of books of ithi’th type.

The next line contains nn integers t1,t2,t3,,tn(1tik)t_1,t_2,t_3,\dots,t_n(1 \leq t_i \leq k), the type of book a student will borrow on the ithi’th day.

It is guaranteed that sum of nn in all the test cases doesn’t exceed 200.

Output

Print the minimum real number ss, that if students pay ss% of the purchasing price as rent and you buy and return books optimally then you’ll not lose any money after serving all the students. Errors less than 10610^{-6}will be ignored.

Sample

InputOutput
3
4 1 2
2 4
1 2
1 2 1 2
6 2 2
2 4
1 2
1 2 1 2 2 2
6 2 3
5 7 11
4 2 4
1 3 1 2 1 3
50
15
31.8181818182

In the first case, you can only keep one book at a time on your shelves. So before buying a new book you must return any book bought before. So, the optimal buying and returning strategy will be:

Night before day one, return nothing, buy book 1.

Night before day two, return book 1, buy book 2.

Night before day three, return book 2, buy book 1.

Night before day four, return book 1, buy book 2.

Night after day four, return book 2, buy nothing.

If you follow this, you’ll spend 2+4+2+4=12 units of money buying books and gain 1+2+1+2=6 units of money returning books. If you take 50% as rent, then rent collected will be 1+2+1+2=6 which enables you to run the library with no loss.

In the second example, you have 2 storage spaces, so you can buy both books before the first day and sell them after serving everyone.

In the third example, one of the optimal buying and returning strategies will be,

Night before day one, return nothing, buy book 1,3.

Night before day two, return nothing, buy nothing.

Night before day three, return nothing, buy nothing.

Night before day four, return book 1, buy book 2.

Night before day five, return book 2, buy book 1.

Night before day six, return nothing, buy nothing.

Night after day six, return book 1,3, buy nothing.


Discussion

Statistics


0% Solution Ratio

Submit

Login to submit

Editorial

The value of sss will be in range (0,100)(0,100)(0,100). We will do a binary search on the value of ...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.