Một robot cứu hỏa xuất phát tại trạm cứu hỏa \(A\) cần đến thị trấn \(Z\) (nơi xảy ra hỏa hoạn) để làm nhiệm vụ cứu hỏa. Đường đi của robot là một đường thẳng, khi xuất phát robot cách thị trấn \(Z\) một khoảng là \(L\) đơn vị độ dài và robot chứa \(P\) đơn vị năng lượng; cứ đi mỗi đơn vị khoảng cách robot phải tốn 1 đơn vị năng lượng. Trên con đường từ trạm cứu hỏa \(A\) đến thị trấn \(Z\ \)có \(N\) trạm cung cấp năng lượng được đánh số từ 1 đến \(N\). Trạm cung cấp năng lượng thứ \(i\) cách thị trấn \(Z\) một khoảng bằng \(D_{i}\) đơn vị độ dài và có khả năng cung cấp tối đa \(C\)_i đơn vị năng lượng.

Robot cần đến thị trấn nhanh nhất để kịp thời cứu hỏa nên cần giảm thiểu tối đa việc dừng lại tại các trạm cung cấp để tiếp thêm năng lượng nếu có thể. Giả thiết rằng robot không có giới hạn về lượng năng lượng nạp thêm tại các trạm cung cấp.

Yêu cầu: Xác định số lượng tối thiểu các trạm cung cấp năng lượng mà robot phải dừng lại tiếp thêm năng lượng để có thể đến được thị trấn \(Z\).

Dữ liệu:

+ Dòng đầu tiên chứa số \(T\ (T\ \leq \ 5)\) là số lượng bộ dữ liệu;

+ Sau đó là \(T\) nhóm dòng, mỗi nhóm là một bộ dữ liệu có dạng:

• Dòng 1: chứa số nguyên dương \(N\ (1\ \leq \ N\ \leq \ 10\)⁵\()\) là số trạm cung cấp năng lượng.

• Trong \(N\) dòng tiếp theo, mỗi dòng chứa hai số \(D_{i}\) và \(C\)_i\(\ (1\ \leq \ D\)_i\(\ \leq \ 10\)⁶\(,\ 1\ \leq \ C\)_i\(\ \leq \ 1000)\) là khoảng cách từ trạm cung cấp thứ \(i\) đến thị trấn \(Z\) và khả năng cung cấp năng lượng của trạm ấy. Dữ liệu đảm bảo \(D_{1} > D_{2} > \ldots > D_{N}\).

• Dòng cuối của nhóm chứa hai số nguyên \(L\) và \(P\) \((D_{1}\ \leq \ L\ \leq \ 10\)⁶\(,\ 2\ \leq \ P\ \leq \ 10\)⁶\()\) là khoảng cách từ trạm cứu hỏa \(A\) đến thị trấn \(Z\) và lượng năng lượng của robot lúc xuất phát.

Kết quả:

+ Gồm \(T\) dòng, mỗi dòng ghi số lượng tối thiểu các trạm cung cấp năng lượng cần dừng lại để tiếp thêm năng lượng sao cho robot có thể đến được thị trấn \(Z\) ứng với mỗi bộ dữ liệu. Với bộ dữ liệu mà robot không thể đến được thị trấn \(Z\) thì ghi -1. Thứ tự in kết quả là thứ xuất hiện của bộ dữ liệu trong Input

Ví dụ:

Ràng buộc:

• Có 4 test có \(1\ \leq \ N\ \leq \ 100\);

• Có 2 test có \(100\ < \ N\ \leq \ 10^{5}\ .\)