Maximum Non-Overlapping Intervals Sum

You are given N intervals. Each interval is given by two integers \(x\) and \(y\), which represents that there are \(y-x+1\) piles of premium grass available in the range from \(x\) to \(y\) (inclusive). You can select any set of intervals, provided that no two chosen intervals share any common part (i.e. they must be non-overlapping). The goal is to help the cow maximize the total number of grass piles it can eat.

Note: Two intervals \([x_1,y_1]\) and \([x_2,y_2]\) are considered non overlapping if \(y_1 < x_2\) or \(y_2 < x_1\).

Input: The first line contains an integer \(N\), the number of intervals. Then \(N\) lines follow, each containing two integers \(x\) and \(y\).

Output: Output a single integer denoting the maximum total number of grass piles that can be achieved by selecting a subset of non overlapping intervals.

inputFormat

The first line contains an integer N, indicating the number of intervals. Each of the next N lines contains two space-separated integers x and y representing an interval from x to y (inclusive).

outputFormat

Output a single integer representing the maximum sum of grass piles that can be obtained by selecting a set of non overlapping intervals.

sample

3
1 3
2 5
6 8

7