Early or Late - Repovive Starter Round 3 | 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

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

12G. Early or Late

Constraints

Input

Output

Samples

12G. Early or Late

Constraints

Input

Output

Samples