16549번 - Pie Max Flow 다국어

문제

There is a graph with N + 1 vertices numbered 0 to N. For 1 ≤ i ≤ N, an edge with capacity A_i connects vertices 0 and N. For 1 ≤ i ≤ N, an edge with capacity B_i connects vertices i and ((i mod N) + 1). There are no other edges in the graph. All edges are undirected.

A flow in a graph from a source vertex s to a sink vertex t assigns to each edge e = (v₁, v₂) a direction (either v₁ → v₂ or v₂ → v₁) and a number Fe such that 0 ≤ F_e ≤ K_e, where K_e is the capacity of edge e. We say that there are F_e units of flow in the specified direction, out of v₁ or v₂, and into the other vertex. Every flow must satisfy the constraint that for each vertex v except the source and sink, the sum of the flows out of v equals the sum of the flows into v. The maximum flow from s to t is the maximum over all flows from s to t of the sum of flows out of s minus the sum of flows into s.

Let C_i be the maximum flow from vertex 0 to vertex i. Find the value of C₁ + · · · + C_N.

Sequences A and B will not be given directly. Instead N, A₁, B₁ and integers P, Q, W, X are given. Then for i > 1:

• A_i = (PA_i−1) mod Q
• B_i = (WB_i−1) mod X

입력

Line 1 contains one integer N (2 ≤ N ≤ 2²⁰).

Line 2 contains three integers A₁, P, Q (1 ≤ A₁, P, Q ≤ 2²⁹).

Line 3 contains three integers B₁, W, X (1 ≤ B₁, W, X ≤ 2²⁹).

출력

Print one line with one integer, the value of C₁ + · · · + C_N.

제한

힌트

For the first example, A = [7, 1, 2, 4, 8], B = [5, 4, 1, 3, 9], C = [20, 9, 7, 8, 20]. The graph is shown below.