Maximum Total Working Time

You are given n tasks. Each task is represented by an interval [s_i, e_i), where s_i is the start time and e_i is the finish time of the i^th task. Your goal is to select a subset of non-overlapping tasks (i.e. tasks that do not conflict in time) in order to maximize the total working time.

The total working time is defined mathematically as:

[ Total\ Working\ Time = \sum_{i \in S} (e_i - s_i) ]

where S is the set of chosen tasks. Note that two tasks are non-overlapping if the start time of a task is not less than the finish time of the previously selected task.

You need to compute and output the maximum possible total working time achievable using the available tasks.

inputFormat

The input is given via stdin as follows:

• The first line contains a single integer n, which is the number of tasks.
• The next n lines each contain two space-separated integers s and e, representing the start time and finish time of a task, respectively.

outputFormat

Output a single integer via stdout representing the maximum total working time that can be achieved by selecting a subset of non-overlapping tasks.

3
1 3
2 5
4 7

5