Cảm thấy có lỗi vì tất cả những trò nghịch ngợm mà mình đã gây ra quanh trang trại gần đây, Bessie đồng ý giúp Nông dân John xếp chồng một lô kiện cỏ khô sắp được chuyển đến.

Ban đầu có \(N\) (\(1 \le N \le 1\,000\,000\), \(N\) lẻ) chồng trống, được đánh số từ \(1\) đến \(N\). Sau đó, FJ đưa cho Bessie một dãy gồm \(K\) chỉ dẫn (\(1 \le K \le 25\,000\)), mỗi chỉ dẫn có dạng A B, nghĩa là Bessie phải thêm một kiện cỏ khô mới lên trên mỗi chồng trong đoạn từ \(A\) đến \(B\). Ví dụ, nếu Bessie nhận được chỉ dẫn 10 13, cô phải thêm một kiện cỏ khô vào từng chồng \(10\), \(11\), \(12\) và \(13\).

Sau khi Bessie xếp các kiện cỏ theo chỉ dẫn của FJ, ông muốn biết chiều cao trung vị của \(N\) chồng — tức là chiều cao của chồng nằm giữa nếu sắp xếp các chồng theo thứ tự chiều cao (thuận tiện thay, \(N\) là số lẻ nên chồng này là duy nhất). Hãy giúp Bessie xác định câu trả lời cho câu hỏi của FJ.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) cách nhau bởi dấu cách.
• \(K\) dòng tiếp theo, mỗi dòng chứa một chỉ dẫn của FJ dưới dạng hai số nguyên \(A\) và \(B\) cách nhau bởi dấu cách (\(1 \le A \le B \le N\)).

Dữ liệu ra

• Dòng đầu tiên chứa chiều cao trung vị của một chồng sau khi Bessie hoàn thành các chỉ dẫn.

Ví dụ

7 4
5 5
2 4
4 6
3 5

1

Nguồn

USACO 2012 January Contest, Bronze Division — Haybale Stacking

Tác giả đề: Brian Dean, 2012.