STJEPAN - Beer Machines

no tags 

 

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 Li liters of beer but will have energy to walk at most Di seconds (that is Di units of length), he will walk to beer machine Stjepan suggests him and as soon as machine produces Li liters of beer tourist will be able to enjoy it.

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 minimal sum of passed times from arrival of tourist to getting a beer. If a tourist can't get a beer then his time is 0.

Note that tourists are independent and machines can be used multiple times.

Input

On 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, C) each and they describe arrays P, T, A, L and D, respectively.
With these four numbers i-th element of array is defined as Xi = 1 + ((Xi-1*A + B) mod C), where indices are 1-based and X0 is given in input.

1 ≤ X0, A, B, C ≤ 109.

Note: Author's solution doesn't depend on properties of pseudo-random generator.

Output

Output total time from task statement. Answer will fit in 64-bit signed integer.

Example

Input:
3 4
3 4 1 4 3 6 2 4 4 10 3 8 1 10 3 1 8 7 1 3 2 6
1 3 2
Output: 53
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


Added by:Ivan Katanic
Date:2010-07-27
Time limit:1.277s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6
Resource:own problem