J. 视频质量

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

彩彩是偶像天团Pastel*Palettes的主唱,经常在视频网站上发布视频,并且喜欢自我检索。

彩彩在视频网站上拥有 个粉丝,并且发布了 个视频,编号为 。粉丝会为编号连续的视频点赞,其中第 个粉丝选择为 (表示大于等于 并且严格小于 的整数范围)的视频点赞。该网站对视频质量有两个评价指标 分别表示:

  • 最小的整数 ,表示从作者的个粉丝中 个粉丝,使得全部的视频都被选中的粉丝点赞过;
  • 最小的整数 ,表示从作者的个粉丝中 个粉丝,使得全部的视频都被选中的粉丝点赞过。

现在彩彩想要计算 ,以此来判断自己的视频质量。可是彩彩不会算,因此把任务交给了作为彩黑警察的你。

输入格式

第一行两个整数 表示彩彩的粉丝数量和视频数量。

接下来 行,每行两个整数 ,表示第个粉丝给 范围的视频点赞。

题目保证所有视频都至少被点赞过一次。

输出格式

输出一行,两个整数中间用空格隔开,分别表示要计算的

样例

样例输入1

3 3
0 2
1 3
1 2

样例输出1

2 3

样例输入2

2 4
0 4
0 4

样例输出2

1 1

样例输入3

5 4
0 2
2 4
0 3
1 3
3 4

样例输出3

2 4