Bài 5

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 sang 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 < \cdots < x_n)$.

Để tưới 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ại vị trí cây $t_i$, có bán kính tưới nước là $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.

Nhập từ bàn phím

• Dòng đầu tiên chứa hai số nguyên dương $n, m$ $(1 \le m \le n \le 10^6)$.
• Dòng thứ hai chứa $n$ số nguyên $x_1, x_2, \ldots, x_n$ $(0 < x_1 < x_2 < \cdots < x_n \le 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 \le t_i \le n;\ R_i \le 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)$.

Hai số liên tiếp trên cùng một dòng cách nhau bằng khoảng trống (space).

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

• Có $30\%$ số tests ứng với $30\%$ số điểm của bài có $m = 1$.
• $30\%$ số tests tiếp theo ứng với $30\%$ số điểm của bài có $n \le 2000$.
• Các tests còn lại không có giới hạn bổ sung.