Rabbit Lunch

Time limit8sMemory limit512 MB

Summary

Given counts of M carrot kinds and N kiwi kinds generated by recurrences, find the maximum number of distinct (carrot kind, kiwi kind) pairs a rabbit can take, one carrot and one kiwi each.

Level: Medium7 of 10
Topics: Greedy, Sorting, Math, Implementation
Solved: No attempts yet

Problem

A rabbit eats one carrot and one kiwi for lunch. Rabbits are very distinctive, so there must not be two different rabbits that eat the same kind of carrot and the same kind of kiwi.

There are $M$ kinds of carrots. There are $m_i$ carrots of the $i$ -th kind. There are $N$ kinds of kiwis. There are $n_i$ kiwis of the $i$ -th kind. Find the maximum number of rabbits that can eat lunch.

Generate $m_i$ and $n_i$ using the following recurrences.

$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)$

Input

The input is given in the following format:

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

Output

Print one integer on a single line: the maximum number of rabbits that can eat lunch.

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.

Examples2

Example 1
Input
```
2 3 1 3 1 0
```
Expected output
```
2
```
Example 2
Input
```
5 8 1 2 3 4
```
Expected output
```
19
```