| Codeforces Round 132 (Div. 2) |
|---|
| Закончено |
Цепная передача Васиного велосипеда состоит из двух частей: n звездочек закреплены на оси педалей, а m звездочек — на оси заднего колеса. С помощью цепи вращение педалей передается на заднее колесо.
Известно, что i-ая звездочка на оси педалей имеет ai (0 < a1 < a2 < ... < an) зубьев, а j-ая звездочка на оси заднего колеса имеет bj (0 < b1 < b2 < ... < bm) зубьев. Любая пара (i, j) (1 ≤ i ≤ n; 1 ≤ j ≤ m) называется передачей и задает номера звездочек, на которых в данный момент закреплена цепь. Для передачи (i, j) передаточное число равно величине 
.
Так как Васе нравятся целые числа, он хочет найти такие передачи (i, j), что их передаточные числа целые. С другой стороны, Васе нравится быстрая езда, поэтому среди всех «целочисленных» передач (i, j), он хочет выбрать передачи с максимальным передаточным числом. Помогите ему найти количество таких передач.
В задаче дробь обозначает деление в вещественных числах, то есть округление не производится.
В первой строке входных данных записано целое число n (1 ≤ n ≤ 50) — количество звездочек на оси педалей велосипеда. Во второй строке записаны n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 104) в порядке строгого возрастания.
В третьей строке входных данных записано целое число m (1 ≤ m ≤ 50) — количество звездочек на оси заднего колеса. В четвертой строке записаны m целых чисел b1, b2, ..., bm (1 ≤ bi ≤ 104) в порядке строгого возрастания.
Гарантируется, что существует хотя бы одна передача (i, j), что ее передаточное число — целое. Числа в строках разделяются пробелами.
Выведите количество «целочисленных» передач, которые имеют максимальное значение передаточного числа среди всех «целочисленных» передач.
2
4 5
3
12 13 15
2
4
1 2 3 4
5
10 11 12 13 14
1
В первом примере максимальное целое передаточное число равно 3. Существуют две передачи, которые имеют такое передаточное число. Для одной из них a1 = 4, b1 = 12, а для другой a2 = 5, b3 = 15.
