问题描述

一群瞎眼的蚂蚁被某同学弄到了一根铁丝上，铁丝可以看成一条线段。蚂蚁们必须要从铁丝上下去，不然某同学又会不知道如何虐待他们了。蚂蚁的移动速度都是1，但是个头有大有小。只要身体完全离开铁丝的两端就算离开铁丝。不巧的是蚂蚁不知道该往哪一段移动最快，所以他们约定每只蚂蚁都随便朝一个方向走，每当两个蚂蚁身体碰在一起的时候，他们两个就同时改为原来相反方向(反弹)，速率不变。（假设瞬间转身）

请问你，最好情况下需要多久时间(最快)使得所有蚂蚁都逃离铁丝。

除此之外某同学还要问你最坏情况下(最慢)所有蚂蚁都逃离铁丝的时间。

输入格式

第一行两个整数分别表示蚂蚁个数和铁丝长度。

接下来行，每行两个整数分别表示一只蚂蚁的身长和初始位置。

（可以理解铁丝左端是，右端是。初始位置代表每只蚂蚁的左端）

数据保证初始位置时蚂蚁身体互不相交，且不会完全脱离铁丝。

输出格式

第一行输出最短时间。

第二行输出最长时间。

输入样例blind.in

2 5
1 1
1 4

输出样例blind.out

2
5

解释：-1--2

最短时间方案：两只蚂蚁做相离运动，2单位时间后蚂蚁完全离开

-1--2
1----
-----

最长时间方案：两只蚂蚁都向左运动，5单位时间后蚂蚁完全离开

			-1--2
			1--2-
			--2--
			-2---
			2----
			-----

数据范围

50%的数据满足：1<=n<=10,m<=100

100%的数据满足：1<=n<=10000;1<=m<=10^6