Practice on Toph

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

Camila and Books

By Sumaiya_18 · Limits 1s, 512 MB

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 $K$ books from her favourite book shop where different types of books are available.

There are total $X$ books of total $N$ types in the book shop. There are total $N$ types of books so, no type is missing, that means there is at least one book available for each type from $1$ to $N$ th type. But there is a condition for her by the shop. That is,

• She can buy either the i -th type book or (N+1-i ) -th type book.

And for example, if $N$=$10$, Camila buys any book of $6$ th type, then she can’t buy any book from $(10+1-6)$ $=$ $5$ th type and vice versa. It is guaranteed that $N$ 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 $K$ books? Or report if it is not possible to buy exactly $K$ books.

Input

The first line contains an integer $T$ $(1≤T≤50)$.Then $T$ test cases follow

The first line of each testcase contains three integers $X$,$N$, $K$ $(1≤X,N,K≤1000, N \leq X)$ 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 $N$ is an even number.

The second line of each testcase contains $X$ space-separated integers $a_1$,$a_2$,….,$a_x$ $(1≤a_i≤1000)$ where $a_i$denotes the type of the $i$-th book.

The third line of each testcase contains $X$ space-separated integers $b_1$,$b_2$,…..,$b_x$ $(1≤b_i≤10^9)$ where $b_i$ denotes the price of the $i$-th book.

Output

Print a single integer for each testcase—the minimum possible price to buy exactly $K$ books. If it is not possible to buy exactly $K$ books, print $-1$ (without quotes).

Sample

InputOutput
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

Note:

In the first example, she can buy two books from $1$st type with prices $1$,$4$ and one book from $2$nd type with price $11$ and total price of these three books is $16$, which is minimum.

Statistics

80% Solution Ratio

likhon5Fastest, 0.1s

Shuvo_MalakarLightest, 4.3 MB

antihashShortest, 1434B

Submit

 Replay of CodeSpark 2021 5M ago CodeSpark 2021 6M ago 