e-olymp

Юстас-Алексу

После блестяще проведенной операции Штирлиц смог определить численность фашистской армии. Естественно такую информацию уже четыре года как ждут в штабе советской армии. Чтобы общаться со штабом Штирлиц использует n радистов. Каждый из радистов должен передать сообщение от Штирлица в штаб. Штирлиц, как хитрый разведчик, зашифровал свое послание таким образом: каждому из радистов он дал одно и то же число - численность армии, но в своей системе счисления, да еще так, что все основания систем счисления у радистов попарно взаимно простые. После передачи радиограммы ищейки Мюллера смогли определить последний символ каждого из сообщений. Вы работаете штатным программистом и должны определить, какое минимальное число мог послать Штирлиц в своем сообщении. Мюллер в отличие от вас не очень любит бинарный код, поэтому он хочет, чтобы искомое число вы вывели в десятичной системе.

Входные данные

В первой строке задается число n - количество радистов у Штирлица. В следующей строке находятся n чисел ai - основания систем счисления, в которых Штирлиц давал сообщения радистам (2ai36 ). В третьей строке через пробел записано n символов ci - последние буквы каждого из сообщений (0ci < ai; ci - либо цифра от 0 до 9, либо буква от A до Z).

Выходные данные

Вывести минимальное число, которое мог передать Штирлиц в десятичной системе счисления.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
2
6 13
1 B
Выходные данные
37
Автор А. Миланин