author: Guangda Huzhang 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1196
You have \(S\) candies in your hands, and there are \(M\) machines in front of you. Now you can do following operations:
- If you have candies, you can put all your candies into the i-th machine (you can't keep any candies).
Then waiting for a while, the i-th machine will return you \([(A_i \times n + B_i) \mod P]\) candies if you put \(n\) candies into it.
- Do nothing, you still have your candies.
If your goal is to get \(T\) candies at last, what is the minimum number of times you need to operate machines.
Input includes several test cases. For each test case, the first line contains four non-negative integers \(S, T, M, P (P > 0, M \times P \leq 10^6)\). The following \(M\) lines contain details of \(M\) machines. For each line, there are two integers \(A_i, B_i\).
We guarantee every integer of input is in the range of 32-bit signed integer.
The input ends by EOF.
For each test case, if you can get \(T\) candies at last, output a single integer indicates the minimum number of operations, otherwise output -1.
3 1 2 4 1 1 1 2
Time limit: 500 msec
Memory limit: 64 MB