#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/12/problems/G

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Early or Late - Repovive Starter Round 3 | Repovive | Repovive

12G. Early or Late

3500 pts2s256 MB

You are given $n$ jobs. You must do all jobs in some order.

For each job $i$ , two integers $a_i$ and $b_i$ are given.

If job $i$ is done among the first $a_i$ jobs of the order, it gives you $b_i$ points. Otherwise, it gives you $-b_i$ points.

Choose the order of the jobs to maximize the total number of points.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$
$0 \le a_i \le n$
$-10^9 \le 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} ans \end{array} \right\} \times t

Samples

Input

Case 1

1
0
5

Case 2

3
1 2 0
10 -5 7

Case 3

4
2 0 4 1
3 -8 -2 6

Case 4

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

Case 5

6
1 6 2 4 0 3
-10 2 8 -6 7 -1

Explanation

Case 1

The only possible order is [1]. Since job 1 is not among the first 0 jobs, its contribution is -5.

Case 2

One optimal order is [1, 3, 2]. The contributions are 10, -7, and 5, so the total score is 8.

Case 3

One optimal order is [4, 1, 2, 3]. The contributions are 6, 3, 8, and -2, so the total score is 15.

Case 4

One optimal order is [2, 4, 3, 1, 5]. The contributions are 10, 3, 7, -4, and -5, so the total score is 13.

Case 5

One optimal order is [2, 3, 1, 5, 4, 6]. The contributions are 2, 8, 10, -7, 6, and 1, so the total score is 20.

Output

Case 1

-5

Case 2

Case 3

Case 4

Case 5

You are given $n$ jobs. You must do all jobs in some order.

For each job $i$ , two integers $a_i$ and $b_i$ are given.

If job $i$ is done among the first $a_i$ jobs of the order, it gives you $b_i$ points. Otherwise, it gives you $-b_i$ points.

Choose the order of the jobs to maximize the total number of points.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$
$0 \le a_i \le n$
$-10^9 \le 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} ans \end{array} \right\} \times t

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

12G. Early or Late

Constraints

Input

Output

Samples

12G. Early or Late

Constraints

Input

Output

Samples