有一个 n 层高的楼,电梯会在 1 ~ n 层之间运行。每次运行结束后,电梯都会自动停靠在 x 层。假设一个人想从第 5 层到第 10 层,那么电梯会先从第 x 层(因为之前已经自动停靠在 x 层了)走到第 5 层,然后从第 5 层走到第 10 层,最后再从第 10 层回到自动停靠的楼层 x 层。电梯总共会行走 |x-5|+|5-10|+|10-x| 的距离(其中 |x| 表示 x 的绝对值)

现在已知 m 个人依次乘坐电梯,每个人都会在电梯自动停靠在 x 层之后才乘坐。第 i 个人乘坐电梯是从 a 层移动到 b 层。现在 x 由你设置,你需要让电梯的总行走距离最短。请你输出对应的 x 和最短的行走距离。若有多个可能的 x ,输出最小的一个。

第一行包含两个正整数 n , m ,表示楼的层数和乘坐电梯的人数。

接下来包含 m 行,每行给出两个数字 a_{i}, b_{i}(a_{i}\lt b_{i}) ,意义如题面所示。

输出两个数字,第一个数字表示电梯自动停靠的楼层,第二个数字表示电梯行走的最短距离。

【样例1 说明】

电梯一开始自动停靠在位置 4,第一个人想要从第 3 层走到第 7 层。则电梯共行走 |4-3|+|3-7|+|7-4|=8 。第二个人想要从第 4 层行走到第 6 层,行走之后电梯停靠回第四层,电梯共行走 8+|4-6|+|6-4|=12 。若电梯自动停靠在 5 或 6,则总行走距离也是 12,但是对于多个可能的 x ,应 该输出最小值。

【数据范围】

对于 20% 的数据,有 1 ≤n , m ≤100

对于 50% 的数据,有 1 ≤n , m ≤2000

对于另外 20% 的数据,对于任意的 i(1 \leq i \lt m) 有 a_{i} \lt b_{i} \lt a_{i+1} \lt b_{i+1}

对于 100% 的数据,有 1 ≤n , m ≤5 * 10^{5} , 1 ≤a , b ≤n