Meximus Minimus - Repovive Premier Round 4 | Repovive

9B. Meximus Minimus

1000 pts1s256 MB

You are given two arrays $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$ .

For a subset $S$ , define its score as:

mex(\{b_i \mid i \in S\}) \times \sum_{i \in S} a_i

Here, $mex$ of a multiset of integers is the smallest non-negative integer that does not appear in it.

Now Meximus Minimus Decimus Meridius, Prime Minister of Repovive land, wants to partition set $\{1,2,,\ldots,n\}$ into exactly $k$ none-empty subsets such that sum of scores of these subsets is minimized. Find this minimum value.

Constraints

$1 \le t \le 10^4$
$1 \le k \le n \le 2 \times 10^5$
$0 \le a_i \le 10^6$
$0 \le b_i \le n$
The sum of $n$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ b_1 \quad b_2 \quad \cdots \quad b_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

4 1
2 3 1 5
0 1 3 1

Case 2

5 2
10 4 7 2 8
0 2 1 0 3

Case 3

3 2
5 6 7
1 2 3

Case 4

4 3
1 2 3 4
0 0 0 0

Case 5

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

Explanation

Case 1

All indices must be placed in one subset. The MEX of the values $0,1,3,1$ is $2$ , and the sum of the corresponding $a_i$ values is $11$ , so the score is $22$ .

Case 2

One optimal partition is $\{1,4\}$ and $\{2,3,5\}$ . The first subset has score $1 \times 12 = 12$ , and the second subset has MEX $0$ , so its score is $0$ .

Case 3

There is no index with $b_i=0$ . Therefore, both subsets can have MEX $0$ , and the total score is $0$ .

Case 4

Every index has $b_i=0$ . No matter how the indices are partitioned, each subset has MEX $1$ , so the total score is $1+2+3+4=10$ .

Case 5

All indices must be placed in one subset. The MEX of the values $0,1,2,3,4$ is $5$ , and the sum of the corresponding $a_i$ values is $15$ , so the score is $75$ .

Output

Case 1

Case 2

Case 3

Case 4

Case 5

You are given two arrays $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$ .

For a subset $S$ , define its score as:

mex(\{b_i \mid i \in S\}) \times \sum_{i \in S} a_i

Here, $mex$ of a multiset of integers is the smallest non-negative integer that does not appear in it.

$1 \le t \le 10^4$
$1 \le k \le n \le 2 \times 10^5$
$0 \le a_i \le 10^6$
$0 \le b_i \le n$
The sum of $n$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ b_1 \quad b_2 \quad \cdots \quad b_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

All indices must be placed in one subset. The MEX of the values $0,1,3,1$ is $2$ , and the sum of the corresponding $a_i$ values is $11$ , so the score is $22$ .

One optimal partition is $\{1,4\}$ and $\{2,3,5\}$ . The first subset has score $1 \times 12 = 12$ , and the second subset has MEX $0$ , so its score is $0$ .

There is no index with $b_i=0$ . Therefore, both subsets can have MEX $0$ , and the total score is $0$ .

Every index has $b_i=0$ . No matter how the indices are partitioned, each subset has MEX $1$ , so the total score is $1+2+3+4=10$ .

All indices must be placed in one subset. The MEX of the values $0,1,2,3,4$ is $5$ , and the sum of the corresponding $a_i$ values is $15$ , so the score is $75$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

9B. Meximus Minimus

Constraints

Input

Output

Samples

9B. Meximus Minimus

Constraints

Input

Output

Samples