返回小组 开始 2019-11-03 08:30:00

201910月赛(普及组)

结束 2019-11-07 21:30:00
Contest is over.
当前 2024-11-22 09:52:41

D. 游园会

描述

学校打算在周末办一个游园会。游园会包括n个游戏项目,每一个游戏项目分别在s_i时间开始,在 t_i 时间结束。对于每一个项目,你都可以选择是否参加,但是一旦参加了某个项目,你就必须完成,不得中途退出。此外,参加项目的时间不能重叠(即使是开始的瞬间和结束的瞬间的重叠也是不允许的)。

小明想要报名参加游园会,并且尽可能多的完成游园会的游戏项目,你可以帮助小明选择项目吗?

输入

第一行为一个整数n,代表共有n个游戏项目;

第二行为n个整数,第 i 个数代表项目 i 开始的时间s_i,两个数之间使用空格分隔;

第三行为n个整数,第 i 个数代表项目 i 结束的时间t_i,两个数之间使用空格分隔。

输出

输出数据为一行一个整数,表示小明最多可以选择多少个游戏项目。

样例

输入

5
1 2 4 6 8
3 5 7 9 10

输出

3

提示

对于100%的数据:1\leq N\leq 10^51\leq s_i\leq t_i\leq 10^9


Submit

登录

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