Người ta tin rằng không lâu sau khi cải sang Kitô giáo, Mindaugas, vị vua đầu tiên và duy nhất của Litva, đã ra lệnh xây dựng Nhà thờ chính tòa Vilnius. Công trình gần hoàn thành, chỉ còn sàn nhà cần được lát bằng những viên gạch gốm tráng men có hoa văn.

Sàn nhà thờ là một đa giác trên mặt phẳng hai chiều với hệ tọa độ Descartes. Đa giác có \(N\) đỉnh phân biệt, được đánh số từ \(1\) đến \(N\). Với mỗi \(1\le i\le N\), đỉnh \(i\) nằm tại \((X[i],Y[i])\), trong đó \(X[i]\) và \(Y[i]\) là các số nguyên không âm. Có một cạnh nối đỉnh \(i\) với đỉnh \(i+1\) với mỗi \(1\le i\le N-1\), và một cạnh nối đỉnh \(N\) với đỉnh \(1\). Các đỉnh được liệt kê theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ.

Mỗi cạnh của đa giác song song với trục \(x\) hoặc trục \(y\). Ngoài ra, đa giác là đa giác đơn, nghĩa là:

• Tại mỗi đỉnh có đúng hai cạnh gặp nhau.
• Hai cạnh bất kỳ chỉ có thể gặp nhau tại một đỉnh.

Những người thợ có vô hạn viên gạch. Mỗi viên là một hình vuông có cạnh bằng \(2\). Họ muốn lát một phần lớn sàn nhà thờ bằng những viên gạch này. Cụ thể, họ muốn chọn một đường thẳng đứng rồi lát phần sàn nằm bên trái đường thẳng đó. Với mỗi số nguyên \(k\), gọi \(L_k\) là đường thẳng đứng gồm các điểm có hoành độ bằng \(k\). Một cách lát phần sàn bên trái \(L_k\) là một cách đặt một số viên gạch trên mặt phẳng sao cho:

• Mỗi điểm nằm trong miền trong của đa giác và có hoành độ nhỏ hơn \(k\) đều được một viên gạch phủ lên.
• Không có điểm nào nằm ngoài đa giác hoặc có hoành độ lớn hơn \(k\) bị một viên gạch phủ lên.
• Miền trong của các viên gạch không chồng lên nhau.

Hoành độ nhỏ nhất trong các đỉnh của đa giác là \(0\). Gọi \(M\) là hoành độ lớn nhất trong các đỉnh.

Hãy giúp những người thợ tìm số nguyên \(k\) lớn nhất sao cho \(k\le M\) và có thể lát phần sàn nhà thờ bên trái \(L_k\). Lưu ý rằng theo định nghĩa, luôn có thể lát phần sàn bên trái \(L_0\) bằng cách dùng \(0\) viên gạch.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), lần lượt là số đỉnh và hoành độ lớn nhất của một đỉnh.

Tiếp theo là \(N\) dòng. Dòng thứ \(i\) chứa hai số nguyên \(x_i\) và \(y_i\) là tọa độ đỉnh thứ \(i\); đây là các tọa độ được ký hiệu \(X[i]\) và \(Y[i]\) ở trên. Các đỉnh được liệt kê theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ.

Dữ liệu ra

In ra giá trị \(k\) lớn nhất sao cho \(k\le M\) và có thể lát phần sàn nhà thờ bên trái \(L_k\).

Ràng buộc

• \(4\le N\le 2\cdot 10^5\).
• \(1\le M\le 10^9\).
• \(0\le y_i\le 10^9\) với mọi \(1\le i\le N\).
• Sàn nhà thờ tạo thành một đa giác đơn có các cạnh song song với các trục tọa độ.
• Giá trị nhỏ nhất trong \(x_1,x_2,\ldots,x_N\) là \(0\), và giá trị lớn nhất là \(M\).

Phân nhóm

1. \(4\) điểm: \(N=4\).
2. \(9\) điểm: \(N\le 6\).
3. \(11\) điểm: \(x_N=0\), \(y_N=0\), đồng thời \(x_i\le x_{i+1}\) và \(y_i\ge y_{i+1}\) với mọi \(1\le i\le N-2\).
4. \(19\) điểm: \(M\le 1000\) và \(y_i\le 1000\) với mọi \(1\le i\le N\).
5. \(22\) điểm: \(y_i\) chẵn với mọi \(1\le i\le N\).
6. \(25\) điểm: \(x_i\) chẵn với mọi \(1\le i\le N\).
7. \(10\) điểm: không có ràng buộc bổ sung.

Ví dụ

14 6
0 1
0 3
2 3
2 4
0 4
0 6
3 6
3 7
4 7
6 7
6 5
3 5
3 2
3 1

2

4 3
0 0
0 3
3 3
3 0

0

18 9
0 2
2 2
2 1
4 1
4 0
9 0
9 2
4 2
4 4
7 4
7 3
9 3
9 6
4 6
4 5
2 5
2 4
0 4

6