## STJEPAN - 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 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_{0}, 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_{0} is given in input.

1 ≤ X_{0}, A, B, C ≤ 10^{9}.

**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 43 4 1 4 3 6 2 4 4 10 3 8 1 10 3 1 8 7 1 3 2 61 3 2Output: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 |