商场导购

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

作为H国知名商人,你在D城的市中心开了一家高人气商场,商场提供极其贴心的五星级导购服务。需要导购服务的顾客可以提前一天预约使用的时间段。目前有NN位顾客预约了第二天导购服务,其中第i位顾客预约的时间段为AiA_iBiB_i,注意导购服务包括了AiA_iBiB_i两个时间段。很明显一位导购在同一个时间段只能服务一位客户。为了节约人工成本,你希望使用最少的导购满足全部顾客的要求。请你帮他求出第二天最少需要多少位导购。

Format

Input

输入有两行,第一行为两个正整数,表示预约导购服务的顾客数量。第2到NN+1行,每行两个整数AiA_iBiB_i,表示第i位顾客预约的时间段。

Output

输出一个整数,表示最少需要多少导购,可以满足全部顾客。输出一个整数,表示最少需要多少导购,可以满足全部顾客。

Samples

5
1 10
2 5
5 8
3 6
6 10
4
10
24 29
11 14
5 10
26 32
4 6
27 31
39 39
39 44
18 21
18 18
3

【样例1说明】

由于导购服务包括边界的时间段,所以[2, 5]和[5, 8]必须让不同的导购负责,那么只有[2, 5]和[6, 10]可以请同一个导购,其他都需要单独请导购。

Limitation

对于30%的数据:1≤N≤10;

对于60%的数据:1≤N≤100,1≤Ai≤Bi≤100;

对于100%的数据:1≤N≤10000,1≤Ai≤Bi≤5000。

菜就多练

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
23
Start at
2024-3-2 19:00
End at
1970-1-1 8:00
Duration
-474827 hour(s)
Host
Partic.
0