#125. Thiết bị phun nước (WATER)

Một bãi cỏ dài mét, rộng mét được lắp đặt thiết bị phun nước (vòi phun). Mỗi vòi phun được lắp đặt trên đường trung tâm của bãi cỏ (cách hai bên mép chiều rộng mét). Chúng ta biết vị trí của mỗi vòi phun (khoảng cách từ đầu bên trái của đường trung tâm) và bán kính tưới nước mà nó có thể bao phủ.

Hỏi: Để tưới ướt toàn bộ bãi cỏ cùng lúc, cần mở ít nhất bao nhiêu vòi phun?

Dữ liệu:

• Input bao gồm nhiều bộ dữ liệu kiểm tra (test cases).
• Dòng đầu tiên chứa một số nguyên biểu thị số lượng bộ dữ liệu.
• Dòng đầu tiên của mỗi bộ dữ liệu chứa các số nguyên , và .
• dòng tiếp theo, mỗi dòng chứa hai số nguyên, cho biết vị trí và bán kính tưới của một vòi phun (hình minh họa ở trên mô tả trường hợp của bộ dữ liệu mẫu đầu tiên).

Kết quả:

• Với mỗi bộ dữ liệu, xuất ra một số biểu thị số lượng vòi phun tối thiểu cần thiết để tưới toàn bộ bãi cỏ. Nếu mở tất cả vòi phun mà vẫn không thể tưới hết bãi cỏ, xuất ra .

Ví dụ:

Dữ liệu:

3
8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4
3 10 1
3 5
9 3
6 1
3 10 1
5 3
1 1
9 1

Kết quả:

6
2
-1

Giới hạn:

• Đối với dữ liệu, .