Hôm nay Mr.Maru phải đi làm việc tại một ngân hàng. Vào ngày làm việc đầu tiên của anh, anh đã gặp một rắc rối lớn, ngân hàng mà anh đang làm việc đang bị đe dọa bởi một siêu trộm khét tiếng trên thế giới. Với mục tiêu là vượt qua m (0 ≤ m ≤ 1e6) cửa sắt để lấy được viên kim cương quý giá. Để vượt qua được i cửa thì nếu ông ta có được một trong số những thẻ ID sau: \(Li - (Li + 1) - ,...,\) và \(Ri\) thẻ. Biết rằng siêu trộm đã làm được n (0 ≤ n ≤ 1e6) thẻ từ trước đó.

REQUEST

• Hãy cho biết số thẻ để siêu trộm có thể một mình vượt qua tất cả các cửa.

Input format

• Dòng đầu tiên là các số nguyên n, m.
• Dòng tiếp theo là:

L1 R1
L2 R2
L3 R3
...
Lm Rm

Output format

• In ra kết quả bài toán.

Example

Sample Input

10 3
3 6
5 7
6 9

Sample Output

1