Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Problem F:
RabbitLunch

  うさぎは昼食ににんじんとキウイを1 個ずつ食べる. うさぎはとても個性的なので, 食べるにんじんの種類もキウイの種類も同じであるような, 異なる2 匹のうさぎが存在してはならない.

  にんじんは $M$ 種類ある. $i$ 種類目のにんじんは $m_i$ 個ある. キウイは $N$ 種類ある. $i$ 種類目のキウイは $n_i$ 個ある. 最大何匹のうさぎが昼食をとれるか求めよ.

  $m_i$ と $n_i$ は次の漸化式を用いて生成せよ.

 $m_0 = m0$ 

 $m_{i+1} = (m_i * 58 + md )$ mod $(N + 1)$

 $n_0 = n0$

 $n_{i+1} = (n_i * 58 + nd )$ mod $(M + 1)$

Constraints

$M$ will be between 1 and 2,500,000, inclusive.

$N$ will be between 1 and 2,500,000, inclusive.

$m0$ and $md$ will be between 0 and $N$, inclusive.

$n0$ and $nd$ will be between 0 and $M$, inclusive.

Input

  入力は以下の形式で与えられる:

  

$M$ $N$ $m0$ $md$ $n0$ $nd$

Output

昼食をとれるうさぎの匹数の最大値を表す整数を 1 行に出力せよ.

Sample Input 1

2 3 1 3 1 0

Sample Output 1

2

Sample Input 2

5 8 1 2 3 4

Sample Output 2

19


Sample input:
2 3 1 3 1 0


Sample output:
2

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    M, N, m0, md, n0, nd = map(int, readline().split())

    S = [0]*(M+1)
    S[0] = mi = m0
    for i in range(1, M):
        S[i] = mi = (mi * 58 + md) % (N + 1)
    S.sort()
    for i in range(M):
        S[i+1] += S[i]

    T = [0]*(N+1)
    T[0] = ni = n0
    for i in range(1, N):
        T[i] = ni = (ni * 58 + nd) % (M + 1)
    T.sort()
    for i in range(N):
        T[i+1] += T[i]

    def gen():
        def calc(a, b):
            return (M - a)*(N - b) + S[a] + T[b]
        yield 10**18
        j = N
        for i in range(M+1):
            while j > 0 and calc(i, j) > calc(i, j-1):
                j -= 1
            yield calc(i, j)
    write("%d\n" % min(gen()))
solve()