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

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.

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.

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).

Input | Output |
---|---|

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 $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. |

80% Solution Ratio

adnan_tokyEarliest,

likhon5Fastest, 0.1s

Shuvo_MalakarLightest, 4.3 MB

antihashShortest, 1434B

Login to submit

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

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