Skip to content

11196: 【原1196】Candy



author: Guangda Huzhang 原OJ链接:


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 Format

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.

Output Format

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.

Sample Input

3 1 2 4
1 1
1 2

Sample Output


Case Limits

Time limit: 500 msec

Memory limit: 64 MB

Oops! 本题目还没有解答!