No Self-Purchase - Repovive Premier Round 7 | Repovive

20C. No Self-Purchase

1500 pts2s256 MB

There are $n$ people in a market. Person $i$ :

owns one item for sale at price $a_i$ ;
wants to buy one item and is willing to pay at most $b_i$ .

A transaction consists of person $i$ buying the item owned by person $j$ . The transaction is allowed if $i \ne j$ and $a_j \le b_i$ .

Each person may buy at most one item, and each person's item may be sold at most once. A person is allowed to sell their item and buy another person's item.

Find the maximum possible number of transactions.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$
$1 \le a_i, b_i \le 10^9$

Input

t

\left. \begin{array}{l} n \\ 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} \mathrm{answer} \end{array} \right\} \times t

Samples

Input

Case 1

1
5
10

Case 2

2
1 2
2 1

Case 3

3
1 100 200
1 100 200

Case 4

4
5 2 4 1
1 2 3 5

Case 5

5
4 1 7 3 2
3 7 2 4 1

Explanation

Case 1

The only person cannot buy their own item, so no transaction is possible.

Case 2

Person $1$ can buy person $2$ 's item, and person $2$ can buy person $1$ 's item.

Case 3

Two transactions are possible: person $2$ buys person $1$ 's item, and person $3$ buys person $2$ 's item. Person $1$ cannot buy another person's item.

Case 4

Three transactions can be made by letting persons $2$ , $3$ , and $4$ buy the items of persons $4$ , $2$ , and $1$ , respectively. Four transactions are impossible because persons $1$ and $2$ would both need the only item they can buy from someone else, which is person $4$ 's item.

Case 5

All five people can buy an item. In order, they may buy the items of persons $4$ , $3$ , $5$ , $1$ , and $2$ .

Output

Case 1

Case 2

Case 3

Case 4

Case 5

There are $n$ people in a market. Person $i$ :

owns one item for sale at price $a_i$ ;
wants to buy one item and is willing to pay at most $b_i$ .

A transaction consists of person $i$ buying the item owned by person $j$ . The transaction is allowed if $i \ne j$ and $a_j \le b_i$ .

Each person may buy at most one item, and each person's item may be sold at most once. A person is allowed to sell their item and buy another person's item.

Find the maximum possible number of transactions.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$
$1 \le a_i, b_i \le 10^9$

t

\left. \begin{array}{l} n \\ 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} \mathrm{answer} \end{array} \right\} \times t

Person $1$ can buy person $2$ 's item, and person $2$ can buy person $1$ 's item.

Two transactions are possible: person $2$ buys person $1$ 's item, and person $3$ buys person $2$ 's item. Person $1$ cannot buy another person's item.

All five people can buy an item. In order, they may buy the items of persons $4$ , $3$ , $5$ , $1$ , and $2$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

20C. No Self-Purchase

Constraints

Input

Output

Samples

20C. No Self-Purchase

Constraints

Input

Output

Samples