Beer Machines
Little Stjepan lives in a village which can be represented as X-axis. In village there are N beer machines, machine i has x coordinate Pi and needs Ti seconds to produce 1 liter of beer.
This year M tourists( one by one because there is only one guide, Stjepan ) will visit his village, tourist i will arrive at point Ai, want to drink [
As Stjepan wants all tourists to come next year too he will choose machine for each tourist so that tourist can get a beer as soon as possible. Help Stjepan to do that and write program which will output total passed time from arrival of tourist to getting a beer. If tourist can't get a beer then his time is 0.
Note that tourists are independent and machines can be used multiple times.
InputOn first line of standard input you are given two integers (2 ≤ N ≤ 250 000, 1 ≤ M ≤ 500 000), number of beer machines and number of tourists.
Next 5 lines contain 4 integers( X0, A, B, [
Next 5 lines contain 4 integers( X0, A, B, [
] ) each and they describe arrays [], T, A, L and D, respectively.
With these four numbers i-th element of array is defined as Xi = 1 + ( ( X(i-1) * A + B ) mod C ), where indices are 1-based and X0 is given in input.
1 ≤ X0, A, B, C <= 10^9.
Note: Author's solution doesn't depend on properties of pseudo-random generator.
OutputOutput total time from task statement.
Input:
[c]3 4
1 4 3 6
2 4 4 10
3 8 1 10
3 1 8 7
1 3 2 6
Output:
53[p]
Explanation:
Machines( P, T ) : ( 2, 3 ), ( 6, 7 ), ( 4, 3 )
Tourists( A, L, D ) : ( 6, 5, 6 ), ( 10, 7, 3 ), ( 2, 2, 6 ), ( 8, 4, 3 )
Tourist #1-> Machine #3 -> 17 time units
Tourist #2 -> No beer :( -> 0 time units
Tourist #3 -> Machine #1 -> 6 time units
Tourist #4 -> Machine #2 -> 30 time units
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.