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

There are total XX books of total NN types in the book shop. There are total NN types of books so, no type is missing, that means there is at least one book available for each type from 11 to NN 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 NN=1010, Camila buys any book of 66 th type, then she can’t buy any book from (10+16)(10+1-6) == 55 th type and vice versa. It is guaranteed that NN 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 KK books? Or report if it is not possible to buy exactly KK books.

Input

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

The first line of each testcase contains three integers XX,NN, KK (1X,N,K1000,NX)(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 NN is an even number.

The second line of each testcase contains XX space-separated integers a1a_1,a2a_2,….,axa_x (1ai1000)(1≤a_i≤1000) where aia_idenotes the type of the ii-th book.

The third line of each testcase contains XX space-separated integers b1b_1,b2b_2,…..,bxb_x (1bi109)(1≤b_i≤10^9) where bib_i denotes the price of the ii-th book.

Output

Print a single integer for each testcase—the minimum possible price to buy exactly KK books. If it is not possible to buy exactly KK books, print 1-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 11st type with prices 11,44 and one book from 22nd type with price 1111 and total price of these three books is 1616, which is minimum.


    Discussion

    Statistics


    80% Solution Ratio

    adnan_tokyEarliest, 2M ago

    likhon5Fastest, 0.1s

    Shuvo_MalakarLightest, 4.3 MB

    antihashShortest, 1434B

    Submit

    Login to submit

    Editorial

    This problem can be solved by DPDPDP. For each type iii, Camila has three choices −-− buy i−i-i−th t...

    Related Contests

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