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ạ độ xi (x1 < x2 < ... < xn).

Để 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, ..., m) được lắp tại vị trí cây ti, có bán kính tưới nước là Ri. Điều này có ý nghĩa rằng vòi nước này tưới được cây ti và tất cả các cây có khoảng cách đến ti không vượt quá Ri.

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:

Nhập từ bàn phím

- Dòng đầu tiên chứa hai số nguyên dương n, m (1 <= m <= n <= 10^6)

- Dòng thứ hai chứa n số nguyên x1, x2, ..., xn (0 < x1 < x2 < ... < xn <= 10^9) lần lượt là toạ độ 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 ti, Ri (1 <= ti <= n; Ri <= 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, ..., 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)

Kết quả:

Ghi ra màn hình 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

- 30% số tests tiếp theo ứng với 30% số điểm của bài có n <= 2000

- Các tests còn lại không có giới hạn bổ sung

Ví dụ:

Dữ liệu:
5 2
1 3 5 7 9
1 5
4 2

Kết quả:
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 3, 4, 5. Như vậy chỉ các cây 1, 2, 3, 4, 5 được tưới nước.