每条赛道的长度都是 m,并且第 i 段长度为 1 的路面,要么是水泥地,要么是泥地。
题目给出第 i 段水泥地覆盖的赛道范围为 [li,ri],也就是说:
多多是一名赛车手,今天他来到一个特殊的赛车场。这个赛车场有 n 条平行的赛道,每条赛道的长度都是 m 米。赛道由两种路面组成:水泥地和泥地。
水泥地共有 m 段,其中第 i 段水泥地位于距离起点 i−1 米的位置,覆盖了从第 i 条到第 n 条赛道(包括两端),长度为 1 米。
多多驾驶赛车时:
在水泥地上的速度为 1 米 / 秒
在泥地上的速度为 0.5 米 / 秒
多多可以选取任何一条赛道出发,出发之后不允许变道。他现在想知道最快多少时间到达终点,如果有多条赛道满足最快时间,他希望选取赛道编号最小的。
第一行包含两个整数 n,m(1≤n,m≤100000)
接下来 n 行,每行包含两个数字 li,ri(1≤li≤ri≤n),表示第 i 段水泥地覆盖的赛道范围
输出一行,包含两个数字,表示到达终点的最快时间 和选取的赛道编号。
输入
3 2
1 2
2 3
输出
2 2
说明
多多选择第 2 条赛道时:
第 1 米:水泥地(1 秒)
第 2 米:水泥地(1 秒)
总时间最短为 2 秒。