conqueringOlympus

Truyền thuyết kể là nếu một người có thể leo đến đỉnh núi Olympus và trả lời được câu hỏi của các vị thần thì người đó sẽ có một điều ước. Có một người leo núi sau khi leo được n bậc thang thì gặp được các vị thần ngự trên đỉnh. Người đứng đầu các vị thần, Zeus đã hỏi người đó số bậc thang dẫn đến đỉnh, nếu người đó trả lời đúng, điều ước của anh ta sẽ trở thành hiện thực. Người leo núi chỉ biết số bậc thang nằm trong đoạn từ a đến b nên anh ta xin Zeus hãy cho anh ta thêm gợi ý. Zeus đồng ý và cho anh ta k gợi ý không trùng nhau. Mỗi gợi ý gồm có hai thành phần là x và y. Biết rằng y là số dư của phép chia số bậc thang n cho x. Cho hai số a, b là giới hạn của số bậc thang (a <= n <= b) và ma trận chứa thông tin về các gợi ý của Zeus, mỗi mảng con có hai phần tử lần lượt tương ứng với x và y. Hãy cho biết có thể xác định được số bậc thang không. Nếu xác định được, hãy trả về giá trị đó, nếu không, hãy trả về -1.

Ví dụ:

• Với a = 1 b = 100
query = [[3,0],[2,1],[9,3],[7,5]] thì đáp án của hàm countStair sẽ là 75
• Với a=100, b=1000
query = [[2,1],[3,0]] thì không xác định được nên đáp án của hàm countStair sẽ là -1

[Đầu ra/Đầu vào]

• [Thời gian chạy] 1 giây với C++, 6 giây với Java và C#, 8 giây với Python, Go và Js.

• [Đầu vào] integer a, integer b là giới hạn dưới và giới hạn trên của số bậc thang.
  matrix of integer query có k phần tử, mỗi phần tử là một mảng con có hai phần tử lần lượt tương ứng với x và y
0 <= a < b <= 10^6
0 =< y < x <= 10^6

• [Đầu ra] số bậc thang nếu xác định được, nếu không xác định được thì trả về -1