Day of the Programmer- HackerRank problem

 

Problem

Akash got his money from CodeChef today, so he decided to have dinner outside.
He went to a restaurant having $N$ items on the menu. The $i^{th}$ item on the menu belongs to the category $A_i$ and requires $B_i$ time to be cooked.

Akash wants to have a complete meal. Thus, his meal should have at least $K$ distinct categories of food.
The total time required to get all the food Akash orders, is the sum of the cooking time of all the items in the order.

Help Akash find the minimum time required to have a complete meal or tell if it is not possible to do so.

Input Format

• First line will contain $T$, the number of test cases. Then the test cases follow.
• Each test case contains three lines:
  • The first line of each test case contains two space-separated integers $N$ and $K$, denoting the number of dishes on the menu and the number of distinct categories in a complete meal.
  • The second line contains $N$ space-separated integers where the $i^{th}$ integer is $A_i$, denoting the category of the $i^{th}$ dish in the menu.
  • The third line contains $N$ space-separated integers where the $i^{th}$ integer is $B_i$, denoting the time required to cook the $i^{th}$ dish in the menu.

Output Format

For each test case, output in a single line, the minimum time required to have a complete meal.

If it is impossible to have a complete meal, print $-1$ instead.

Constraints

• $1 \leq T \leq 100$
• $1 \leq N,K \leq 10^5$
• $1 \leq A_i \leq 10^5$
• $0 \leq B_i \leq 10^5$
• The sum of $N$ over all test cases won't exceed $10^5$.

Sample 1:

Input

Output

4
3 1
1 2 3
2 1 3
8 3
1 3 2 2 4 1 3 5
3 3 0 1 2 4 1 4
1 1
5
1
5 3
1 1 2 2 1
1 1 0 3 5

1
3
1
-1

Explanation:

Test case $1$: Akash can choose dish with index $2$ having category $2$. The total time required to get the complete meal is $1$.

Test case $2$: Akash can choose dishes with index $3, 5,$ and $7$ from the menu.

• Dish $3$: The dish has category $2$ and requires time $0$.
• Dish $5$: The dish has category $4$ and requires time $2$.
• Dish $7$: The dish has category $3$ and requires time $1$.

Thus, there are $3$ distinct categories and the total time to get the meal is $0+2+1 = 3$. It can be shown that this is the minimum time to get the complete meal.

Test case $3$: Akash can choose the only available dish having category $5$. The total time required to get the complete meal is $1$.

Test case $4$: The total number of distinct categories available is $2$, which is less than $K$. Thus, it is impossible to have a complete meal.

codechef starters 69 problem solution.

Solution:

It will be updated after a few time.