Ngôi trường của Tuấn chuẩn bị kỉ niệm ngày thành lập trường. Nhà trường đã trồng một hàng cây xanh trông rất đẹp. Hàng cây gồm \(n\) cây xanh được đánh số thứ tự từ 1 đến \(n\) (theo hướng từ trái sang phải) và cách đều nhau, tức là khoảng cách giữa hai cây kề nhau là không đổi.

Để tưới nước cho cây, nhà trường có kế hoạch lập đặt \(m\ (1 \le m ≤ n)\) vòi tưới nước tự động. Vòi nước thứ \(i\ (i = 1,2,3,...,m)\) được lắp tại vị trí cây thứ \(X_i\) thì có thể tưới nước cho cây thứ \(X_i\), và \(R_i\) cây liền kề bên trái và \(R_i\) cây liền kề bên phải vòi nước đó, tức là vòi thứ \(i\) sẽ tưới nước được cho cây thứ j nếu \(|j − x_i| ≤ R_i\). \(R_i\) được gọi là bán kính tưới nước của vòi thứ \(i\).

Cho biết vị trí lắp \(m\) vòi nước tại m \(x^2\)cây có số thứ tự là \(X_1, X_2, ..., X_m\ (1 \le X_1 \le X_2 \le ...X_m \le n)\) và các bán kính tưới nước là \(R+1, R_2, ..., R_m\ (1 \le R_1 \le R_2 \le Rm \le 100)\).

Yêu cầu: Tính xem, có bao nhiêu cây được tưới nước khi lắp \(m\) vòi nước tự động như trên. Một cây được tưới nước nếu có ít nhất một vòi nước có thể tưới nước cho cây đó.

Input: Dữ liệu cho trong tệp văn bản HANGCAY.INP gồm:

• Dòng 1 ghi hai số nguyên dương \(n\) và \(m\ (2<n≤2000; 1≤ m ≤ n)\) tương ứng là số cây và số vòi nước.
• \(m\) dòng tiếp theo, dòng thứ \(i\ (i = 1, 2, ...,m)\) ghi hai số nguyên \(X_i, R_i\). Trong đó \(X_i\) là số thứ tự của cây đặt vòi nước thứ \(i\), \(R_i\) là bán kính tưới nước.

Output: Kết quả ghi ra tệp văn bản HANGCAY.OUT gồm một số nguyên duy nhất là số cây được tưới nước

Scoring

• Có 30% số test ứng với 30% số điểm thỏa mãn \(2 ≤ n ≤ 200; m = 1\).
• Có 30% số test ứng với 30% số điểm thỏa mãn \(2 \le n≤200; 2 \le m≤n;\) không có hai vòi nước trở lên có thể cùng tưới nước cho 1 cây.
• Có 40% số test ứng với 40% số điểm thỏa mãn \(200 < n \le 2000;2 \le m \le n\)

Example

8 2
2 2
5 1 

6