Muốn rèn luyện kỹ năng dùng kéo cho thật điêu luyện, Fran nghĩ ra một bài tập mới. Cậu lấy một dải giấy dài ~n~ xăng-ti-mét cùng với một chiếc kéo, rồi nhờ Lana hỗ trợ.

Lana sẽ đưa cho Fran ~k~ chỉ dẫn dạng: Hãy cắt dải thứ ~x~ tại vị trí cách đầu dải ~l~ xăng-ti-mét. Ban đầu Fran chỉ có đúng ~1~ dải giấy. Sau lần cắt đầu tiên, cậu sẽ có ~2~ dải: dải đầu dài ~l~ xăng-ti-mét, và dải còn lại dài ~n-l~ xăng-ti-mét.

Sau đó Fran tiếp tục cắt dải thứ nhất hoặc dải thứ hai, tùy theo chỉ dẫn của Lana. Mỗi khi một dải bị cắt, hai mảnh mới sẽ thay thế dải cũ trong thứ tự hiện tại.

Nói chính xác hơn, giả sử ở một thời điểm Fran đang có ~m~ dải với độ dài ~a_1, a_2, \ldots, a_m~. Nếu Lana bảo cắt dải thứ ~x~ tại vị trí ~l~, thì dãy độ dài mới sẽ trở thành:

~a_1, a_2, \ldots, a_{x-1}, l, a_x-l, a_{x+1}, \ldots, a_m~.

Sau khi thực hiện xong toàn bộ các lần cắt, Fran và Lana muốn kiểm tra lại quá trình. Một cách để làm điều đó là đếm xem ở cuối cùng có bao nhiêu độ dài dải giấy khác nhau. Nhiệm vụ của bạn là tính số lượng này.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~: độ dài ban đầu của dải giấy và số chỉ dẫn mà Lana đưa ra.

Mỗi trong ~k~ dòng tiếp theo chứa hai số ~x_i~ và ~l_i~, nghĩa là ở bước thứ ~i~, Fran phải cắt dải thứ ~x_i~ tại vị trí ~l_i~ xăng-ti-mét tính từ đầu dải đó.

Output

In ra trên một dòng duy nhất số lượng độ dài dải giấy phân biệt mà Fran còn lại sau khi thực hiện xong tất cả các lần cắt.

Ràng buộc

• ~2 \le n \le 500~
• ~1 \le k < n~
• ~1 \le x_i \le i~
• ~1 \le l_i \le L-1~, với ~L~ là độ dài của dải thứ ~x_i~ ở thời điểm hiện tại

Chấm điểm

• Subtask 1 (9 điểm): ~k \le 3~
• Subtask 2 (6 điểm): ~l_i = 1~ với mọi ~i = 1, 2, \ldots, k~
• Subtask 3 (13 điểm): ~x_i = i~ với mọi ~i = 1, 2, \ldots, k~
• Subtask 4 (22 điểm): Không có ràng buộc bổ sung.

Sample Input 1

5 1
1 2

Sample Output 1

2

Sample Input 2

6 2
1 4
1 2

Sample Output 2

1

Sample Input 3

10 3
1 2
2 3
3 2

Sample Output 3

2

Giải thích

• Ví dụ 1: Dãy độ dài biến đổi từ ~[5]~ thành ~[2, 3]~, nên có ~2~ độ dài khác nhau.
• Ví dụ 2: Dãy độ dài biến đổi theo chuỗi ~[6] \to [4, 2] \to [2, 2, 2]~, nên cuối cùng chỉ còn ~1~ độ dài phân biệt.
• Ví dụ 3: Dãy độ dài biến đổi theo chuỗi ~[10] \to [2, 8] \to [2, 3, 5] \to [2, 3, 2, 3]~, nên đáp án là ~2~.