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 toạ độ Ox và cây thứ \(i\) có toạ độ \(x_i\) (\(x_1 < x_2 < \cdots < 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ạ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.

Input

• Dòng đầu tiên 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 \(x_1, x_2, \ldots, x_n\) (\(0 < x_1 < x_2 < \cdots < x_n \leq 10^9\)) lần lượt là toạ độ 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 nước 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)

Output

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

Scoring

• \(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 \leq 2000\)
• Các tests còn lại không có giới hạn bổ sung

Example

6 2
1 3 5 7 9 11
1 5
4 2

5