Trường THCS nơi Dũng đang học có 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 qua phải). Để đơn giản có thể coi hàng cây như trục tọa độ \(Ox\) và cây thứ \(i\) có tọa độ \(x_{i}\) \((x_{1} < x_{2}, < \ldots < x_{n})\).

Để tưới nước cho cây, nhà trường có kế hoạch lắp đặt \(m\) vòi tưới nước tự động. Vòi nước thứ \(i\ (i = 1,2,\ldots,m)\) được lắp đặt tại vị trí cây \(t_{i}\), có bán kính tưới nước \(R_{i}\). Điều này có ý nghĩa rằng vòi nước này tưới được cây \(t_{i}\) và tất cả các cây có khoảng cách đến \(t_{i}\) không vượt quá \(R_{i}\).

Yêu cầu: Cho biết vị trí lắp đặt \(m\) vòi nước và bán kính tưới nước của \(m\) vòi này. Hãy đếm xem có bao nhiêu cây được tưới nước.

Dữ liệu vào:

• Dòng đầu tiên chứa chứa hai số nguyên dương \(n,\ m\ (1 \leq m \leq n \leq 10^{6})\)

• Dòng thứ hai chứa \(n\) số nguyên lần lượt là \(x_{1},x_{2},\ldots,x_{n}\ (0 < x_{1} < x_{2} < \ldots < x_{n} \leq 10^{9})\) lần lượt là tọa độ của các cây \(1,\ 2,\ldots,n\).

• Tiếp theo là \(m\) dòng, dòng thứ \(i\) chứa hai số nguyên dương \(t_{i},\ R_{i}\ (1 \leq t_{i} \leq n;R_{i} \leq 10^{9})\) lần lượt là số hiệu và bán kính tưới nước của vòi thứ \(i\ (i = 1,2,\ldots,m)\).

Kết quả:

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

Ràng buộc:

• Có 30% số tests ứng với 30% số điểm của bài có \(m = 1\)

• Có 30% số tests tiếp theo ứng với 30% số điểm của bài có \(n \leq 2000\)

• Các tests còn lại không có ràng buộc bổ sung.

Ví dụ: