I Am Knowledge

Interview

Time limit2sMemory limit1024 MB

Summary

Given books with a start cost a_i and a finish reward b_i, decide whether some reading order keeps joy from going negative.

Level: Medium5 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

A wizard who lives in a mansion often visits the underground library. One day, the wizard decides to read all $N$ books in the library. Only one book can be read at a time, but the wizard can choose the order.

Starting a book is hard, but after finishing it the wizard gains the joy of acquired knowledge. Joy is an integer, and the wizard starts with joy $0$ . Until all books are read, the wizard repeats the following process.

Choose any unread book.
If the chosen book has number $k$ , spend $a_k$ joy to start reading it. If joy becomes less than $0$ , the wizard falls asleep without finishing the book and cannot read any more books.
If joy does not become less than $0$ and the book is finished, gain $b_k$ joy.

Tell whether the wizard can finish all $N$ books without falling asleep.

Input

The first line contains the number of books $N$ in the library ( $1 \leq N \leq 100\,000$ ).

From the second line, each of the next $N$ lines contains two integers $a_i, b_i$ separated by a space. ( $0 \leq a_i, b_i \leq 10^9$ )

This means that reading book $i$ costs $a_i$ joy, and finishing it gives $b_i$ joy.

Output

Print 1 if the wizard can finish all books in the library, and 0 otherwise.

Examples3

Example 1
Input
```
3
1 3
0 2
1 1
```
Expected output
```
1
```
Example 2
Input
```
2
0 3
4 100
```
Expected output
```
0
```
Example 3
Input
```
4
0 2
3 0
2 2
2 3
```
Expected output
```
1
```