开始 2024-08-23 00:00:00

8.19-8.24集训第五天

结束 2024-08-26 08:00:00
Contest is over.
当前 2024-12-22 09:09:35

D. 和谐俱乐部

描述

某一个私人俱乐部有N个会员,每一个会员都是既美丽又强壮的,我们以A代表强壮,以B代表美丽,但他们都有一个缺点是嫉妒。例如i会员嫉妒j会员的条件是:A_i≤A_j并且B_i≥B_jA_i≥A_j并且B_i≤B_j,但是如果j会员的美丽和强壮都不如i会员,则i会员会忽视j会员的存在。而如果j会员的美丽和强壮都强于i会员的话,则i会员会非常尊敬j会员。

为了庆祝新年的到来,俱乐部经理准备组织一次舞会,但是他担心各会员之间由于嫉妒而引发争斗。所以,邀请哪些会员前来参加舞会实在是伤透了经理的脑筋。那么,精通电脑编程的你,能告诉经理该给哪些会员发放邀请函及发放的最多人数是多少吗?

输入

第一行为整数N,代表N个会员。 剩下N行为每个会员的A值和B值。

输出

输出最大邀请人数。

样例

输入

4
1 1
1 2
2 1
2 2

输出

2

提示

2≤N≤100000,1≤A_i,B_i≤10^9


Submit

登录

注册
时间限制 1 秒
内存限制 128 MB
提交