该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

输入描述

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

接下来包含 $m$ 行，每行给出两个数字 $a_i, b_i$，意义如题面所示。

输出描述

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

10 2
3 7
4 6

4 12

【样例 1 说明】

电梯一开始自动停靠在位置 4，第一个人想要从第 3 层走到第 7 层。则电梯共行走 |4-3|+|3-7|+|7-4|=8。第二个人想要从第 4 层行走到第 6 层，行走之后电梯停靠回第四层，电梯共行走 8 + |4-6|+|6-4|=12。

若电梯自动停靠在 5 或 6，则总行走距离也是 12，但是对于多个可能的 $x$，应该输出最小值

15 4
3 7
2 6
10 13
1 5

5 40

15 7
1 2
1 2
1 2
8 9
10 11
12 13
14 15

8 74

【数据范围】

对于 $20\%$ 的数据，有 $1 \leq n,m \leq 1001≤n,m≤100$

对于 $50\%$ 的数据，有 $1 \leq n,m \leq 20001≤n,m≤2000$

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

对于 $100\%$ 的数据，有 $1 \leq n, m \leq 5*10^5 ，1 \leq a,b \leq n$