Maximum Speech Duration Scheduling

You are given several speeches that must be scheduled in a lecture hall. Each speech is defined by a unique start time and finish time. Two speeches that overlap even partially cannot be held in the same hall. Note that one speech can start exactly at the moment another speech finishes.

Your goal is to choose a subset of non-overlapping speeches so that the total duration of speeches is maximized. If the i-th speech starts at \(s_i\) and finishes at \(f_i\), its duration is \(f_i - s_i\). Formally, you need to maximize \(\sum_{i \in S}(f_i-s_i)\) over all subsets \(S\) of non-overlapping speeches.

inputFormat

The first line contains an integer \(n\) — the number of speeches. Each of the following \(n\) lines contains two integers \(s_i\) and \(f_i\) — the start and finish times of a speech.

outputFormat

Output a single integer — the maximum total duration of non-overlapping speeches.

sample

3
1 3
2 5
4 7

5