Rồng Zmei Gorynich

Con quái vật ban đầu có $x$ cái đầu. Bạn có $n$ loại đòn đánh. Khi tung đòn loại thứ $i$, số đầu hiện tại giảm đi $min(d_i,curX)$, trong đó $curX$ là số đầu hiện tại. Tuy nhiên nếu sau đòn đánh này quái vật vẫn còn ít nhất một cái đầu, nó sẽ mọc thêm $h_i$ cái đầu mới. Nếu $curX=0$ thì quái vật bị tiêu diệt.

Ví dụ: nếu $curX=10$, $d=7$, $h=10$ thì số đầu chuyển thành $13$ (chém rơi $7$ đầu nhưng lại mọc thêm $10$ đầu mới); còn nếu $curX=10$, $d=11$, $h=100$ thì số đầu chuyển thành $0$ và quái vật bị tiêu diệt (không mọc thêm đầu vì không còn đầu nào).

Bạn có thể tung mỗi loại đòn bao nhiêu lần tùy ý, theo thứ tự tùy ý. Hãy tính số đòn ít nhất để tiêu diệt quái vật.

Có $t$ truy vấn độc lập.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$: số lượng truy vấn.
• Với mỗi truy vấn:
  • Dòng đầu chứa hai số nguyên $n$ và $x$: số loại đòn và số đầu ban đầu của quái vật.
  • $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $d_i$ và $h_i$: mô tả đòn đánh loại $i$.

Dữ liệu ra

Với mỗi truy vấn, in ra số đòn ít nhất cần tung để tiêu diệt quái vật. Nếu không thể tiêu diệt được, in ra $-1$.

Ràng buộc

• $1\le t\le 100$
• $1\le n\le 100$, $1\le x\le {10}^9$
• $1\le d_i,h_i\le {10}^9$

Ví dụ