407884: GYM102916 H Video Reviews - 2

Memory Limit:64 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Video Reviews - 2time limit per test4 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard outputEasy problem, just binary search the answer. Oh, wait...You

The studio "Lodka Gaming" is engaged in advertising their new game ".C.O.N.T.E.S.T: Unexpected Behaviour". The studio's marketer is planning to communicate with $$$n$$$ videobloggers one by one (in the predetermined order, starting from the 1-st and ending with the $$$n$$$-th), offering them to record a video review on the game. All people are different and videobloggers are as well, therefore the $$$i$$$-th videoblogger will record a review in two cases: either he is interested in this game, or there are already at least $$$a_i$$$ video reviews on this game.

The studio wants to have at least $$$m$$$ video reviews on the Internet. The game designer of "Lodka Gaming" understands these video reviews possibly would not appear by themselves, so he wants to convince some video bloggers that they are actually interested in this game. Which minimal number of videobloggers are needed to be convinced?

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 5 \cdot 10^7, 1 \le m \le n$$$) — the number of videobloggers and the required number of video reviews.

As $$$n$$$ can be too large, the $$$a_i$$$ values will be generated by linear congruential random number generators.

The second line contains two integers $$$a_1$$$ and $$$k$$$ ($$$0 \le a_i \le 5 \cdot 10^7, 0 \le k \le 10^5$$$).

Each of the following $$$k$$$ lines contains 4 integers $$$c_j$$$, $$$x_j$$$, $$$y_j$$$ and $$$z_j$$$ ($$$1 \le c_j < 5 \cdot 10^7, 1 \le z_j \le 5 \cdot 10^7, 1 \le x_j < z_j, 0 \le y_j < z_j$$$). $$$z_j$$$ are prime numbers. All $$$a_i$$$, except the first one, will be generated using these numbers. The first $$$c_1$$$ of them will be generated using the formula $$$a_i = (x_1 \cdot a_{i-1} + y_1) \mod z_1$$$, the next $$$c_2$$$ — using the formula $$$a_i = (x_2 \cdot a_{i-1} + y_2) \mod z_2$$$, and so on. It is guaranteed that the sum of all $$$c_j$$$ is $$$n-1$$$.

Output

Output a single integer — the minimal number of videobloggers who have to be convinced to record a video review on the game in order to achieve at least $$$m$$$ total video reviews on the Internet.

ExamplesInput
7 4
2 6
1 1 49999990 49999991
1 1 2 49999991
1 1 0 49999991
1 1 1 49999991
1 1 49999989 49999991
1 1 1 49999991
Output
1
Input
7 4
2 5
1 1 96 97
1 1 2 97
1 1 0 97
1 1 1 97
2 1 96 97
Output
2
Note

In the first sample, $$$a = [2, 1, 3, 3, 4, 2, 3]$$$.

In the second sample, $$$a = [2, 1, 3, 3, 4, 3, 2]$$$.

加入题单

上一题 下一题 算法标签: