# 11196: 【原1196】Candy

### 题目描述

author: Guangda Huzhang 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1196

## Description

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

1


## Case Limits

Time limit: 500 msec

Memory limit: 64 MB

## Oops! 本题目还没有解答！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。