Xếp Chồng

Cho $N$ ngăn xếp (đánh số từ 1 đến $N$, $N$ lẻ), ban đầu đều rỗng. Thực hiện $K$ thao tác, mỗi thao tác thêm 1 đơn vị vào tất cả ngăn trong đoạn $[A,B]$.

Sau khi thực hiện xong, hãy tìm giá trị trung vị (giá trị ở vị trí giữa khi sắp xếp).

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $K$
• $K$ dòng tiếp theo: Hai số nguyên $A_i$ và $B_i$

Dữ liệu ra

• In ra giá trị trung vị.

Ràng buộc

• $1\le N\le 1000000$ ($N$ lẻ)
• $1\le K\le 25000$

Ví dụ