Hàng cây sân trường

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 \leq m \leq 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| \leq 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\) cây có số thứ tự là \(X_1,X_2, ..., X_m\) \((1 \leq X_1 \leq X_2 < ... < X_m \leq n)\) và các bán kính tưới nước là \(R_1,R_2, ..., R_m\) \((1\leq R_1, R_2,..., R_m \leq 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

Vào từ file HANGCAY.INP:

• Dòng đầu ghi hai số nguyên dương \(n\) và \(m\) (\(2 \le n \le 2000\), \(1 \le m \le n\)) --- số cây và số vòi tưới nước.

• \(m\) dòng tiếp theo, dòng thứ \(i\) ghi hai số nguyên \(X_i, R_i\) (\(1 \le X_i \le n\), \(1 \le R_i \le 100\)).

Output

Ghi ra file HANGCAY.OUT:

• Ghi ra một số nguyên duy nhất là số cây được tưới nước.

Example

8 2
2 2
5 1

6

Scoring

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(2 \leq n \leq 200, m = 1\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(2 \leq n \leq 200, 2 \leq m \leq n\).
• Có \(40\%\) số test tương ứng với \(40\%\) số điểm có \(200 < n \leq 2000, 2 \leq m \leq n\).