JumpingOnPoints

Little Petya likes points on a plane a lot. Recently he has received a set of N points from his mother. Points are numbered with integers from 0 to N-1. The i-th point has coordinates (X[i], Y[i]). The only thing Petya likes more than points is playing with little Masha. She suggested that they should play a simple game with his set of points. Masha wrote two numbers P[i] and T[i] on each point. Afterwards, she drew some arrows between the points according to the following rule: There is an arrow from point i to point j if and only if min(|X[i] - X[j]|, |Y[i] - Y[j]|) <= P[i]. Note that the property uses the value P[i] of the source point. If P[i] and P[j] differ, it is possible that there is an arrow in one direction but not in the other.

At the beginning of the game the children put a chip on the point S. In every turn they move the chip along any arrow that is directed from the current point to some other one. When they move a chip from the i-th point to the j-th one, they get max(T[i], T[j]) penalty points. Petya found this game boring very soon, because no one wins or loses here. Instead of just playing the game arbitrarily, Petya decided to focus on minimizing the penalty points. For each point K (from 0 to N-1, inclusive) Petya wants to answer the following question: "What is the smallest total number of penalty points I can receive if I want to move the chip from S to K?

As N can be very large, you will have to generate X[i], Y[i], P[i] and T[i] in your program. In order to do this you are given int[] params that contains 16 ints. Use the following pseudocode to generate X, Y, P and T:

X[0] = params[0];
Y[0] = params[4];
P[0] = params[8];
T[0] = params[12];
for (i = 1; i < N; i++) {
    X[i] = (X[i - 1] * params[1] + params[2]) % params[3];
    Y[i] = (Y[i - 1] * params[5] + params[6]) % params[7];
    P[i] = (P[i - 1] * params[9] + params[10]) % params[11];
    T[i] = (T[i - 1] * params[13] + params[14]) % params[15];
}

Note that if two points with different indices have the same coordinates, they are still treated as two different points.

Your goal is to find D[i] - the smallest number of penalty points that can be achieved when moving the chip to the i-th point from the point S for all i from 0 to N - 1. If the i-th point is unreachable we assume that D[i] = 1.5 * 10^14. Return the sum of D[i] for all i from 0 to N - 1.