Pintu and Fruits
All submissions for this problem are available.### Read problem statements in [Hindi](http://www.codechef.com/download/translated/MARCH20/hindi/CHPINTU.pdf), [Bengali](http://www.codechef.com/download/translated/MARCH20/bengali/CHPINTU.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/MARCH20/mandarin/CHPINTU.pdf), [Russian](http://www.codechef.com/download/translated/MARCH20/russian/CHPINTU.pdf), and [Vietnamese](http://www.codechef.com/download/translated/MARCH20/vietnamese/CHPINTU.pdf) as well. Chef went to Australia and saw the destruction caused by bushfires, which made him sad, so he decided to help the animals by feeding them fruits. First, he went to purchase fruits from Pintu. Pintu sells $M$ different types of fruits (numbered $1$ through $M$). He sells them in $N$ baskets (numbered $1$ through $N$), where for each valid $i$, the $i$-th basket costs $P_i$ and it contains fruits of type $F_i$. Chef does not have too much money, so he cannot afford to buy everything; instead, he wants to choose one of the $M$ available types and purchase all the baskets containing fruits of that type. Help Chef choose the type of fruit to buy such that he buys at least one basket and the total cost of the baskets he buys is the smallest possible. ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first line of each test case contains two space-separated integers $N$ and $M$. - The second line contains $N$ space-separated integers $F_1, F_2, \ldots, F_N$. - The third line contains $N$ space-separated integers $P_1, P_2, \ldots, P_N$. ### Output For each test case, print a single line containing one integer ― the minimum price Chef must pay. ### Constraints - $1 \le T \le 1,000$ - $1 \le M, N \le 50$ - $1 \le F_i \le M$ for each valid $i$ - $0 \le P_i \le 50$ for each valid $i$ ### Subtasks **Subtask #1 (30 points):** $M = 2$ **Subtask #2 (70 points):** original constraints ### Example Input ``` 1 6 4 1 2 3 3 2 2 7 3 9 1 1 1 ``` ### Example Output ``` 5 ``` ### Explanation **Example case 1:** - The sum of all baskets with fruits of type $1$ is $7$. - The sum of all baskets with fruits of type $2$ is $5$. - The sum of all baskets with fruits of type $3$ is $10$. - The sum of all baskets with fruits of type $4$ is $0$ because there are no such baskets. Chef can only choose fruits of type $1$, $2$ or $3$. Therefore, the minimum price he has to pay is $5$.
|Tags||ad-hoc, cakewalk, euler_euler, march20, tmwilliamlin|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, CPP17, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.