Skip to content

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级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!