No testdata at current.

问题描述

马路上总共有n个公交站台，编号从1,2,...,n，有一辆智能公交车会在这n个站台之间穿梭。如果智能公交上没有乘客，那么智能公交就会停靠在x站台。 有人要乘坐智能公交，只需要按动公交站台上的按钮，智能公交就会快到到达相应的站台。 例如，有人想从第五个公交站台到第十个公交站台，那么公交车会先从先从x个站台跑到第五个站台，然后再从第五个站台跑到第十个站台，然后再回到第x站台停下。（智能公交可以随意的双向移动，不需要考虑智能公交是否掉头转弯等因素）假设相邻的两个站台的距离都是 1千米，那么智能公交总共行走了 |x-5|+|5-10|+|10-x|的距离。 现在有m个人要依次乘坐智能公交，每个人都会等待智能公交停在x站台之后在按动当前站台按钮准备乘坐公交。现在已知第i个人都是从a站台到b站台。请你计算x，使得智能公交移动距离最短。最终输出x和最短的距离，x若有多个，输出最小的一个。

输入

第一行两个整数n和m，表示n个公交站，m个乘客.以后的m行表示ai站台到bi站台

输出

智能公交停靠站x

Samples

10 5
2 6
3 8
4 7
9 2
6 1

Limitation

1s, 1024KiB for each test case.