12591259 SUSTech Online Judge

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 633  Solved: 94
[Submit][Status][Web Board]

## Description

YYJ has many magic beads with two colors, red and blue. If a red bead is on the left of a blue bead and they are next to each other, they will disappear and release 1 unit of magic power. YYJ has $$n$$ strings of beads, each string is consists of $$a_i$$ blue beads on the left and $$b_i$$ red beads on the right (To make sure they will disappear). Note that $$a_i$$and $$b_i$$ can be zero.

YYJ now wants to connect these strings in some order and she is wondering how many units of magic power she can get at most.

## Input

The first line contains an integer $$T$$, indicating the number of test cases. For each test case:

The first line contains an integer $$n(1\le n\le 100\ 000)$$, indicating the number of string of beads.

Each of the next $$n$$ lines contains two integers $$a_i, b_i(1\le a_i+b_i\le10\ 000)$$.

It is guaranteed that $$\sum (a_i+b_i)\le500\ 000$$.

## Output

Output one integer, indicating the answer.

## Sample Input

2
2
1 2
2 1
2
1 3
2 1

## Sample Output

2
2

## HINT

We use 'R' to denote red beads and 'B' to denote blue beads.

We have 2 strings: BRR, BBR at first.

The string after connection is: BRRBBR, which can gain 2 units of magic power.

[Submit][Status]