11210번 - Radar 다국어

After your boat ran out of fuel in the middle of the ocean, you have been following the currents for 80 days. Today, you finally got your radar equipment working. And it’s receiving signals!

Alas, the signals come from the “radar” station owned by the eccentric lighthouse keeper Hasse. Hasse’s radar station (which does not work quite like other radar stations) emits continuous signals of three different wave-lengths. Therefore, the only interesting thing you can measure is the phase of a signal as it reaches you. For example, if the signal you tuned on to has a wave-length of 100 meters and you are 1456 meters from the station, your equipment can only tell you that you are either 56, or 156, or 256, or . . . meters away from the lighthouse.

So you reach for your last piece of paper to start calculating – but wait, there’s a catch! On the display you read: “ACCURACY: 3 METERS”. So, in fact, the information you get from this signal is that your distance from Hasse’s radar station is in the union of intervals [53, 59] ∪ [153, 159] ∪ [253, 259] ∪ . . . .

What to do? Since the key to surviving at sea is to be optimistic, you are interested in what the smallest possible distance to the lighthouse could be, given the wavelengths, measurements and accuracies corresponding to the three signals.

Given three positive prime numbers m₁, m₂, m₃ (the wavelengths), three nonnegative integers x₁, x₂, x₃ (the measurements), and three nonnegative integers y₁, y₂, y₃ (the accuracies), find the smallest nonnegative integer z (the smallest possible distance) such that z is within distance y_i from x_i modulo m_i for each i = 1, 2, 3. An integer x' is within distance y from x modulo m if there is some integer t such that x ≡ x' + t (mod m) and |t| ≤ y.

There are three lines of input. The first line is m₁ m₂ m₃, the second is x₁ x₂ x₃ and the third is y₁ y₂ y₃. You may assume that 0 < m_i ≤ 10⁶, 0 ≤ x_i < m_i, and 0 ≤ y_i ≤ 300 for each i. The numbers m₁, m₂, m₃ are all primes and distinct.

Print one line with the answer z. Note that the answer might not fit in a 32-bit integer.