Description

Given $N$ intervals, each with range $[s_i, t_i]$, compute the total length of the union of these intervals.

Input Format

The first line contains a positive integer $N$, representing the number of intervals. Then $N$ lines follow, each containing two positive integers, representing $s_i$ and $t_i$.

Output Format

Output one line with a single positive integer, which is the total length of the union after covering the intervals.

3
1 100000
200001 1000000
100000000 100000001

900002

Hint

For $40 \%$ of the testdata, $N \le 1000$, $1 \le s_i < t_i \le 10000$. For $100 \%$ of the testdata, $N \le 10^5$, $1 \le s_i < t_i \le 10^{17}$.

Translated by ChatGPT 5