#1247. 座位预约

为了防控疫情，图书馆打算实行线上座位预约系统，要求同学们必须在入馆前一天进行预约，声明入馆时间和离馆时间，之后严格按照预约时间入馆、离馆。为使学生座位尽量分散以避免人群聚集，应当摆放尽量少但恰好够用的桌椅。可是究竟需要多少座位才能够用呢？这取决于是否允许学生自选座位：

• 方案 A：要求学生自选座位。同学们入馆前那一天还需要选择一个自己在馆时间段内空余的座位。学生们会遵循一定先后顺序进行选择，“空余”是指后进行选择的同学选定的座位在其就坐的时间段不能被前面选好的同学占用，至于如果有多个空余座位，学生可以按个人喜好选择其中的任意一个。
• 方案 B：不允许自选座位。在每位同学入馆之后，由馆员告知被分配到的的座位。

现在已知 名学生的预约信息，即他们在第二天的入馆、离馆时刻。学校想知道，对于以上两种方案，为保证每名预约的同学都有座位坐，图书馆至少需要布置多少个座位。

容易发现方案 A 占用的座位数依赖于同学们进行选择的顺序以及每名同学选择的座位，但为提高服务质量，学校希望做到不管学生们的选择顺序和每名同学做出的选择是什么，都不会有某名同学选不了座位的情况出现。方案 B 座位的规划由馆员负责，你可以制定馆员的分配策略。

请参见样例 1 以获取更详细的解释。

第一行一个正整数 （）

之后 行，第 行两个正整数 表示第 个学生的入馆时间、离馆时间（）

一行两个正整数 表示 A 方案、B 方案下的最小座位数。

样例输入1

4
1 2
2 3
1 3
3 4

样例输出1

3 2

样例解释

学生A 在 1 时刻入馆，2 时刻离馆；学生 B 在 2 时刻入馆， 3 时刻离馆；学生 C 在1时刻入馆，3 时刻离馆；学生 D 在 3 时刻入馆， 4 时刻离馆。

对于方案 A，2 个座位是不够的，因为如果学生的预约顺序是 ABCD，A 选择了座位 1，B 选择了座位 2，那么轮到 C 选择时，座位预约的情况就会如下表所示，C 来选择时，不存在未被占用的座位了，无法进行选择。

而对方案 A， 3 个座位就已经足够用了。读者可以自行验证所有可能的情况。例如 A 选择了座位 1，B 选择了座位 2，则 C 可以选择座位 3，而 D 可以选择 1,2,3 的任何一个，这里以选 2 为例，此时的座位预约情况表如下：

对于方案 B，2 个座位就是够用的，可以如下表分配座位：

样例输入2

4
1 3
1 3
3 6
3 6

样例输出2

2 2

样例输入3

10
84 302
275 327
364 538
26 364
29 386
545 955
715 965
404 415
903 942
150 402

样例输出3

6 5