Compression Space - Repovive Starter Round 9 | Repovive

25C. Compression Space

1500 pts2s256 MB

A computer stores $n$ files on its disk. File $i$ occupies $a_i$ units of space, and its compressed version occupies $b_i$ units, where $b_i < a_i$ .

To compress a file, the computer first writes its compressed version into free space on the same disk. Only after the compressed version has been written completely does it delete the original file. Thus, the disk must have at least $b_i$ units of free space before file $i$ can be compressed.

You may compress the files in any order, one at a time.

Find the minimum amount of free disk space needed initially to compress all the files.

Constraints

$1 \le n \le 2 \times 10^5$
$1 \le b_i < a_i \le 10^9$
All input values are integers.

Input

\begin{array}{l} n \\ a_1 \quad b_1 \\ a_2 \quad b_2 \\ \vdots \\ a_n \quad b_n \end{array}

Output

\mathrm{answer}

Samples

Input

1
7 3

Explanation

The compressed version needs 3 units of free space. After it is written, the original file can be deleted.

Output

Input

Explanation

Start with 3 free units and compress files 3, 2, and 1, in that order. The free space after each compression is 7, 8, and 10 units.

With fewer than 2 free units, no file can be compressed. With 2 free units, only file 3 can be compressed first. Compressing files 3 and 2 leaves 7 free units, which is not enough for file 1.

Output

Input

Explanation

Start with 1 free unit and compress files 4, 2, 1, and 3. The free space becomes 3, 6, 14, and 16 units, respectively. With no free space, no file can be compressed.

Output

A computer stores $n$ files on its disk. File $i$ occupies $a_i$ units of space, and its compressed version occupies $b_i$ units, where $b_i < a_i$ .

You may compress the files in any order, one at a time.

Find the minimum amount of free disk space needed initially to compress all the files.

$1 \le n \le 2 \times 10^5$
$1 \le b_i < a_i \le 10^9$
All input values are integers.

\begin{array}{l} n \\ a_1 \quad b_1 \\ a_2 \quad b_2 \\ \vdots \\ a_n \quad b_n \end{array}

\mathrm{answer}

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

25C. Compression Space

Constraints

Input

Output

Samples

25C. Compression Space

Constraints

Input

Output

Samples