#1926. 「牛客」电梯停靠 普及−

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

题目描述

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

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

输入格式

第一行包含两个正整数 ,表示楼的层数和乘坐电梯的人数。 接下来包含 行,每行给出两个数字 ,意义如题面所示。

输出格式

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

样例

样例输入 1

10 2
3 7
4 6

样例输出 1

4 12

样例解释 1

电梯一开始自动停靠在位置 ,第一个人想要从第 层走到第 层。则电梯共行走 。 第二个人想要从第 层行走到第 层,行走之后电梯停靠回第四层,电梯共行走 。 若电梯自动停靠在 ,则总行走距离也是 ,但是对于多个可能的 ,应该输出最小值。

样例输入 2

15 4
3 7
2 6
10 13
1 5

样例输出 2

5 40

样例输入 3

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

样例输出 3

8 74

数据范围与提示

  • 对于 的数据,有
  • 对于 的数据,有
  • 对于另外 的数据,对于任意的
  • 对于 的数据,有