Cảm thấy có lỗi cho tất cả các trò nghịch ngợm đã gây ra, Bờm đồng ý giúp cô quản lý thư viện sắp xếp các quyển sách vào ngăn sách của thư viện.

Có N ngăn sách được đánh số từ 1 đến N và ban đầu chúng đều rỗng. Cô thủ thư đưa ra một dãy K hướng dẫn, mỗi hướng dẫn có dạng cặp số nguyên (A, B), có nghĩa Bờm phải đặt vào các ngăn sách từ ngăn A đến ngăn B mỗi ngăn đúng một quyển sách.

Sau khi Bờm hoàn thành xếp sách theo hướng dần của mình, cô thủ thư muốn biết số lượng sách của ngăn chính giữa sau khi sắp xếp lại các ngăn sách theo số lượng sách.

Yêu cầu: Hãy cho biết số lượng sách của ngăn chính giữa sau khi sắp xếp lại các ngăn sách theo số lượng sách.

Dữ liệu vào:

• Dòng 1: Chứa hai số nguyên N, K (1 ≤ N ≤ 10^6 và N là số lẻ; 1 ≤ K ≤ 25000).

• K dòng tiếp theo, mỗi dòng gồm hai số nguyên A, B (1 ≤ A ≤ B ≤ N).

Kết quả ra:

ghi một số nguyên là số lượng sách của ngăn chính giữa sau khi sắp xếp lại các ngăn sách theo số lượng sách.

Sample Input

7 4 
5 5 
2 4 
4 6 
3 5

Sample Output

1