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,\ldots,m)\) được lắp đặt 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 vòi nước đó, tức là vòi thứ \(i\) sẽ tưới nước được cho cây thứ \(j\) nếu \(\left| j - x_{i} \right| \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},\ldots,x_{m}\ (1 \leq x_{1} < x_{2} < \ldots < x_{m} \leq m)\) và bán kính tưới nước là \(r_{1},r_{2},\ldots,r_{m}\ (1 \leq r_{1},r_{2},\ldots,r_{m} \leq 100)\)

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

Dữ liệu vào:

+ Dòng 1 ghi hai số nguyên dương \(n\) và \(m\) \((2 \leq n \leq 2000;1 \leq m \leq 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,\ldots,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.

Kết quả:

+ Ghi một số nguyên duy nhất là kết quả bài toán.

Ví dụ:

Ràng buộc:

+ Có 30% số test tương ứng 30% số điểm có \(2 \leq n \leq 200;m = 1\);

+ Có 30% số test khác ứng với 30% số điểm có \(2 \leq n \leq 200;2 \leq m \leq n\); không có hai vòi nước trở lên có thể cùng tưới 1 cây.

+ Có 40% số test còn lại tương ứng 40% số điểm có \(2 \leq n \leq 2000;2 \leq m \leq n\).