2212. Lecture halls reservation

单点时限: 2.0 sec

内存限制: 256 MB

We have a lecture hall at our disposal. Lecturers place orders in which they specify at what time their lecture begins and at what time it ends. We want to make maximal use of the hall. We accept some orders and reject others and our aim is to achieve the longest possible time of lectures in the hall. We assume that at the moment when one lecture ends another can begin.

Write a program that:

  • reads orders of lecturers,

  • computes the maximal possible time of lectures,

  • writes the result

输入格式

In the first line there is written one positive integer n, n <= 10000, which is the number of orders.

In each of the following n lines there are written two integers p and k, separated by a single space, 0 <= p < k <= 30000. Such a pair of integers represents an order for the hall. The lecture is to begin at time p and end in time k.

输出格式

In the first line there should be written the maximal possible time of lectures.

样例

Input
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
Output
16

4 人解决,10 人已尝试。

4 份提交通过,共有 21 份提交。

8.5 EMB 奖励。

创建: 11 年,6 月前.

修改: 2 年,4 月前.

最后提交: 1 年,7 月前.

来源: POI 1997 III Stage

题目标签
DP