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 P_i and needs T_i 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 A_i, want to drink L_i liters of beer but will have energy to walk at most D_i seconds (that is D_i units of length), he will walk to beer machine Stjepan suggests him and as soon as machine produces L_i 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 (X₀, 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 X_i = 1 + ((X_i-1*A + B) mod C), where indices are 1-based and X₀ is given in input.

1 ≤ X₀, A, B, C ≤ 10⁹.

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
1 4 3 6
2 4 4 10
3 8 1 10
3 1 8 7
1 3 2 6

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.