Stop Overtime!

Interview

Time limit1sMemory limit1024 MB

Summary

Given N tasks with deadlines and required workdays, find the fewest overtime days needed to finish every task on time, or -1 if that is impossible.

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

Problem

The development project consists of $N$ tasks. Each task $i$ requires $t_i$ workdays and must be finished before $d_i$ days pass after the project starts. Regular work alone looks unable to finish every task on time, so Joonmin gives up his personal rest time and works overtime.

The project starts on a Monday. Regular work runs only from Monday to Friday. Overtime can be worked at most once per day regardless of weekday, and one overtime session finishes one day of work.

Input

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

From the second line to the $(N+1)$ th line, each line contains the deadline $d_i$ and the time required $t_i$ for a task, separated by a space. $(1\leq d_i,t_i\leq 100\,000)$

Output

Print the minimum number of overtime days needed to finish all tasks before their deadlines.

If there is no way to finish all tasks before their deadlines, print $-1$ .

Examples2

Example 1
Input
```
5
5 4
6 2
2 1
9 1
10 3
```
Expected output
```
3
```
Example 2
Input
```
3
5 3
3 5
4 3
```
Expected output
```
-1
```