타일

기독교로 개종한 직후, 리투아니아의 첫 번째이자 유일한 왕 민다우가스가 빌뉴스 대성당의 건설을 명령했다고 전해진다. 건설은 거의 끝났고, 바닥에 장식이 있는 유약 세라믹 타일만 깔면 된다.

대성당 바닥은 2차원 직교좌표계 평면 위의 다각형이다. 이 다각형은 서로 다른 $N$개의 꼭짓점을 가지며, 1번부터 $N$번까지 번호가 매겨져 있다. 각 $1 \le i \le N$에 대해 꼭짓점 $i$는 점 $(X_i, Y_i)$에 있고, $X_i$와 $Y_i$는 음이 아닌 정수이다. $1 \le i \le N-1$인 각 $i$에 대해 꼭짓점 $i$와 $i+1$을 잇는 변이 있고, 꼭짓점 $N$과 $1$도 변으로 이어져 있다. 꼭짓점은 시계 방향 또는 반시계 방향 순서로 주어진다.

대성당은 축에 평행한 다각형이다. 즉 모든 변이 $x$축 또는 $y$축에 평행하다. 또한 단순 다각형이다. 각 꼭짓점에서 정확히 두 변이 만나고, 두 변은 꼭짓점에서만 만난다.

건설팀은 한 변의 길이가 2인 정사각형 타일을 무한히 가지고 있다. 팀은 세로선 하나를 고르고, 그 선의 왼쪽에 있는 대성당 부분을 덮고자 한다. 임의의 정수 $k$에 대해 $L_k$는 $x$좌표가 $k$인 세로선이다. $L_k$ 왼쪽 부분을 덮는다는 것은 평면에 타일을 배치하는 것이며, 다음 조건을 만족해야 한다.

• 다각형 내부에 있고 $x$좌표가 $k$보다 작은 모든 점은 어떤 타일로 덮여야 한다.
• 다각형 바깥에 있거나 $x$좌표가 $k$보다 큰 점은 어떤 타일로도 덮이지 않아야 한다.
• 타일의 내부끼리는 겹치지 않아야 한다.

꼭짓점 $x$좌표의 최솟값은 0이다. $M$은 꼭짓점 $x$좌표의 최댓값이다. $k \le M$을 만족하고 $L_k$ 왼쪽 부분을 덮을 수 있는 가장 큰 정수 $k$를 구하라. 정의상 $L_0$ 왼쪽 부분은 타일 0개로 덮을 수 있다.

첫 줄에 정수 $N$과 $M$이 주어진다. $N$은 꼭짓점의 개수이고, $M$은 꼭짓점 $x$좌표의 최댓값이다. 이어지는 $N$개의 줄에는 꼭짓점의 좌표 $x_i$와 $y_i$가 한 줄에 하나씩 주어진다.

$k \le M$이고 $L_k$ 왼쪽 부분을 덮는 배치가 존재하는 가장 큰 정수 $k$를 출력한다.

• $4 \le N \le 2 \cdot 10^5$
• $1 \le M \le 10^9$
• 각 $1 \le i \le N$에 대해 $0 \le y_i \le 10^9$
• 대성당은 축에 평행한 단순 다각형이다.
• $x_1, x_2, \dots, x_N$의 최솟값은 0이고, 최댓값은 $M$이다.