You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

题目描述

喵星边境局势愈发紧张，导致发生边境冲突。喵星军队总司令小袁立即对 $Y$ 星采取军事行动。

整个宇宙可以看作一个平面直角坐标系，城市 $1,2,\dots,n$ 的坐标分别为 $(x_1,y_1),(x_2,y_2),\dots(x_n,y_n)$。

现在小袁率领的若干支舰队（可以理解为小袁的军事力量是无限的）驻扎在边境要塞，城市 $1$ 处。他的舰队会进行以下移动：

• 如果舰队的坐标为 $(x,y)$，那么一天之后它可以移动到 $(x-1,y+2)$ 或 $(x+1,y+2)$ 或 $(x+2,y+1)$ 或 $(x-2,y+1)$ 或 $(x-1,y-2)$ 或 $(x+1,y-2)$ 或 $(x+2,y-1)$ 或 $(x-2,y-1)$ 处。

其中环绕在外的还有一条小行星带，当舰队的坐标 $(x,y)$ 且 $x\le 0$ 或 $y\le 0$ 或 $m < x$ 或 $m < y$ 时，舰队就会撞到小行星带。这是小袁所不想看到的。

现在小袁要攻打城市 $2,3,\dots,n$，每一次他都会从一个已经占领的城市（城市 $1$ 也算），派出舰队前往城市 $i$ 并攻打它，舰队到达之后的第二天城市 $i$ 就被攻占了。

特别的，小袁在一个舰队前往攻打或攻打一个城市的时候不会派出另外一支舰队，在攻占一座城市后当天可以立即派出另外一支舰队。

小袁想问，最少要花多少时间才能攻占所有的城市。

攻打顺序可以不按照 $2,3\dots n$ 的顺序。

输入格式

第一行一个整数 $n,m$，表示城市个数和小行星带的范围。

接下来 $n$ 行，每一行两个正整数 $(x_i,y_i)$，表示城市 $i$ 的坐标。保证 $1\le x_i,y_i \le m$。

输出格式

一个整数 $ans$，表示最少要花的时间。

2 20
1 1
1 3

3

3 150
1 2
2 4
4 3

4

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

23

查看附件的 example4.in

查看附件的 example4.out

提示

样例一解释：

舰队在第一天来到了 $(3,2)$ 的位置，第二天到达了城市 $2$ 的位置，第三天占领了城市 $2$。总共花了 $3$ 天。

样例二解释：

舰队在第一天到达了城市 $2$ 的位置，第二天占领了城市 $2$。第三天到达了城市 $3$ 的位置，第四天占领了城市 $3$。总共花了 $4$ 天。

数据范围

本题采用 Subtask 捆绑测试。

特殊性质：对于每一个 $1\le i\le n-1$，都有 $x_i = x_{i+1}$。

数据严格保证不会有不同的城市拥有相同的坐标。