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 < ... < x_n~).

Để tưới nước cho cây, nhà trường có kế hoạch lắp đặt ~m~ vòi nước tự động. Vòi nước thứ ~i~ (~i = 1, 2, ..., 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 \le m \le n \le 10^6~).
• Dòng thứ hai chứa ~n~ số nguyên ~x_1, x_2, ..., x_n~ (~0 < x_1 < x_2 < ... < x_n \le 10^9~) lần lượt là tọa độ của các cây 1, 2, ..., ~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à chỉ số của cây được lắp vòi nước thứ ~i~ và bán kính tưới nước của vòi thứ ~i~ (~i = 1, 2, ..., m~).

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

Output

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

Sample Input 1

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

Sample Output 1

5

Giải thích: Vòi thứ nhất tưới được các cây số hiệu 1, 2, 3; vòi thứ hai tưới được các cây số hiệu 3, 4, 5. Như vậy các cây 1, 2, 3, 4, 5 được tưới nước.

Subtasks

• 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.