Nilkhet

You’re planning to start a library for the next $n$ 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 $m$ books at a time. To stock the shelves, you will go to the local book market called Nilkhet. At Nilkhet $k$ types of books are available numbered from $1$ to $k$. Each book has a purchasing price $p_i$ and a return price $r_i$. That means you have to pay $p_i$ amount of money to buy the book but after that, if you want to return it the shop will give you $r_i$ money back. It is guaranteed that for all the books $p_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 $m$ 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 $n$ 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 $s$ be a real number that represents the renting rate, meaning if a student wants to borrow a book then they have to pay $s$% 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 $s$, that if students pay $s$% 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( 1 \leq T \leq 100)$ number of test cases.

Each test case starts with 3 integers $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 $k$ integers $p_1,p_2,p_3, \dots ,p_k (1\leq p_i \leq 10^9)$, the purchasing price of books of $i’th$ type.

The next line contains $k$ integers $r_1,r_2,r_3, \dots ,r_k (1\leq r_i < p_i)$, the returning price of books of $i’th$ type.

The next line contains $n$ integers $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 $i’th$ day.

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

Output

Print the minimum real number $s$, that if students pay $s$% 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 $10^{-6}$will be ignored.

Sample

Input	Output
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.