Hide

Back to Studying

The semester’s final exams are approaching rapidly, but Arnar has yet to begin studying. Instead he does what all other Computer Science students do when exams are near: play video games all day long!

But now he’s starting to get worried that he might not have enough time to prepare for all of his exams. He knows the exam schedule, and for each exam he knows how many days he must spend studying for the exam in order to pass. He can only study for at most one exam per day, and he will not be able to do any studying on days when there are exams.

Given this information, help Arnar determine if it is possible for him to study enough to pass all his exams, and, in that case, how many additional days he can spend playing video games before he has to begin studying.

Input

The input consists of:

  • One line with one integer $n$ ($1 \le n \le 2\cdot 10^5$), the number of Arnar’s final exams.

  • $n$ lines, the $i$th of which contains two integers $d_ i$ and $c_ i$ ($1 \le d_ i, c_ i \le 10^9$), the number of days before the $i$th exam and the number of days Arnar must study for this exam in order to pass.

There is at most one exam on any given day.

Output

If there is no way for Arnar to spend the required number of days studying in order to pass all his exams, output “impossible”. Otherwise, output the number of days Arnar can spend playing video games before he has to begin studying in order to pass all his exams.

Sample Input 1 Sample Output 1
2
10 6
20 5
4
Sample Input 2 Sample Output 2
3
6 3
11 4
16 5
2
Sample Input 3 Sample Output 3
1
7 7
0
Sample Input 4 Sample Output 4
2
7 4
10 6
impossible
CPU Time limit 2 seconds
Memory limit 1024 MB
Authors
Arnar Bjarni Arnarson, Bjarki Ágúst Guðmundsson, and Unnar Freyr Erlendsson
Source Reykjavík University Spring Contest 2019
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in