Camila is a multi talented girl and she is always curious about learning something new. She loves to read books but she finds it boring to read any specific category of book for a long time. Now she decides to buy books from her favourite book shop where different types of books are available.
There are total books of total types in the book shop. There are total types of books so, no type is missing, that means there is at least one book available for each type from to th type. But there is a condition for her by the shop. That is,
And for example, if =, Camila buys any book of th type, then she can’t buy any book from th type and vice versa. It is guaranteed that is an even number. Now a days Camila is too busy. Can you help her by telling what will be the minimum possible price if she wants to buy exactly books? Or report if it is not possible to buy exactly books.
The first line contains an integer .Then test cases follow
The first line of each testcase contains three integers ,, — the total number of books,the total number of types of books and the total number of books Camila needs to buy respectfully.It is guaranteed that is an even number.
The second line of each testcase contains space-separated integers ,,…., where denotes the type of the -th book.
The third line of each testcase contains space-separated integers ,,….., where denotes the price of the -th book.
Print a single integer for each testcase—the minimum possible price to buy exactly books. If it is not possible to buy exactly books, print ‘ ’ (without quotes).
3 6 4 3 2 3 4 4 1 1 11 12 6 10 1 4 5 4 2 1 1 2 3 4 40 40 30 20 10 6 2 4 1 2 1 2 1 2 15 20 25 30 35 40
16 30 -1
In the first example, she can buy two books from st type with prices , and one book from nd type with price and total price of these three books is , which is minimum.
Login to submit
This problem can be solved by DPDPDP. For each type iii, Camila has three choices −-− buy i−i-i−th t...