题目描述

我们有许多 OJ 比赛要在 CodesOnline 中举行。每一场比赛都有唯一的起始和终止时间，如果两场比赛的时间有重叠（部分或全部），则它们不能同时举行。我们希望尽可能利用 OJ 平台，平台每小时可盈利 100 元。需要在这些比赛中选择若干场不重叠的比赛，使得总使用时间尽可能长。假设一场比赛结束后（忽略秒数），可以立即开始下一场比赛。

请你编写程序：读入所有比赛的起始和终止时间，计算最大可能的总利益（总使用时间 × 100 元）。

输入格式

第一行包含一个正整数 $n$，表示比赛的总场数。

接下来 $n$ 行，每行包含两个由空格隔开的整数 $p$ 和 $k$，表示一场比赛从时间 $p$ 开始到时间 $k$ 结束。

输出格式

输出一个整数，为最大的利益总和。

样例

12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20

1600

样例解释
可以选择第 3 场（0-4）、第 5 场（7-13）、第 6 场（4-6）、第 11 场（14-16）、第 12 场（18-20），总时长为 $4 + 2 + 9 + 2 + 2 = 19$？等一下，原解释：选择第3个(0-4)、第5个(7-13)、第6个(4-6)、第11个(14-16)、第12个(18-20)，总时长16小时。计算：0-4 长4，4-6 长2，7-13 长6，14-16 长2，18-20 长2，总和4+2+6+2+2=16。所以利益 16×100=1600。因此样例解释正确。

数据范围与提示

• $1 \le n \le 10^4$
• $0 \le p < k \le 3 \times 10^4$
• 时间均为整数，忽略秒数，区间可紧接。

题目来源

2005 省选改编题目