Vasya's bicycle chain drive consists of two parts: n stars are attached to the pedal…
- User
Vasya's bicycle chain drive consists of two parts: n stars are attached to the pedal axle, m stars are attached to the rear wheel axle. The chain helps to rotate the rear wheel by transmitting the pedal rotation.
We know that the i-th star on the pedal axle has ai (0 < a1 < a2 < ... < an) teeth, and the j-th star on the rear wheel axle has bj (0 < b1 < b2 < ... < bm) teeth. Any pair (i, j) (1 ≤ i ≤ n; 1 ≤ j ≤ m) is called a gear and sets the indexes of stars to which the chain is currently attached. Gear (i, j) has a gear ratio, equal to the value .
Since Vasya likes integers, he wants to find such gears (i, j), that their ratios are integers. On the other hand, Vasya likes fast driving, so among all "integer" gears (i, j) he wants to choose a gear with the maximum ratio. Help him to find the number of such gears.
In the problem, fraction denotes division in real numbers, that is, no rounding is performed. Input
The first input line contains integer n (1 ≤ n ≤ 50) — the number of stars on the bicycle's pedal axle. The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 104) in the order of strict increasing.
The third input line contains integer m (1 ≤ m ≤ 50) — the number of stars on the rear wheel axle. The fourth line contains m integers b1, b2, ..., bm (1 ≤ bi ≤ 104) in the order of strict increasing.
It is guaranteed that there exists at least one gear (i, j), that its gear ratio is an integer. The numbers on the lines are separated by spaces.
Output
Print the number of "integer" gears with the maximum ratio among all "integer" gears.
Examples
Input
2 4 5 3 12 13 15
Output
2
Input
4 1 2 3 4 5 10 11 12 13 14
Output
1
Note
In the first sample the maximum "integer" gear ratio equals 3. There are two gears that have such gear ratio. For one of them a1 = 4, b1 = 12, and for the other a2 = 5, b3 = 15.
Assistant
We need to parse the problem: We have two sets of teeth counts: a_i (pedal stars) and b_j (rear wheel stars). For each pair (i, j), ratio is b_j / a_i (since chain connects front and rear sprockets, the gear ratio is rear teeth / front teeth? Actually typical bicycle gear ratio: number of teeth on front chainring and rear cog; the gear ratio is front/back? The problem says gear ratio is value a_i / b_j? Wait it says: "Gear (i, j) has a gear ratio, equal to the value ." There is an image that might represent a fraction, but I need to recall: In many programming problems (like Codeforces 115A? Not sure). Actually I've seen a problem: "Bicycle Chain" (CF #215A maybe). I recall a problem: "A. Bicycle Chain" where given two arrays a (front) and b (rear), find maximum ratio b_j / a_i that is integer and count pairs. Yes, I recall a Codeforces problem "A. Bicycle Chain" where a is front sprocket teeth, b is rear sprocket teeth. The gear ratio is defined as b_j / a_i. And they ask for the number of pairs that give maximum integer ratio. The sample: Input 2; 4 5; 3; 12 13 15; Output 2. Let's test: a=[4,5]; b=[12,13,15]. Compute ratios: 12/4=3; 12/5=2.4; 13/4=3.25; 13/5=2.6; 15/4=3.75; 15/5=3. So integer ratios: 3 (12/4 and 15/5). Maximum integer ratio is 3, count=2. That matches. So indeed ratio = b_j / a_i.
Thus the problem: given two sorted lists a_i (1 ≤ n,m ≤ 50, ai,bi ≤ 10^4). At least one integer ratio exists. Need count of pairs (i,j) such that b_j % a_i == 0 and b_j / a_i is maximum among all such integer ratios.
Approach: For each pair, compute ratio if integer; find maximum ratio; then count pairs with that ratio.
Since n,m are small (≤50), we can just double loop. For each i, j, if b[j] % a[i] == 0, compute q = b[j] / a[i], keep track of max, and maybe store ratios in a list then count. Or simply compute max ratio in first pass, then second pass count pairs with ratio == max. Or combine: compute max as we go and count? But careful: when we see a ratio > current max, we need to reset count. So we can do:
max_ratio = 0, count = 0 for each i: for each j: if b[j] % a[i] == 0: ratio = b[j] // a[i] if ratio > max_ratio: max_ratio = ratio count = 1 elif ratio == max_ratio: count += 1
That's simple.
Constraints tiny, so straightforward.
But we need to parse input: first line n, second line list of a, third line m, fourth line list of b.
Edge Cases: multiple same a_i or b_j? They are strictly increasing, so distinct.
But there could be multiple pairs with same max ratio, count them.
Implement solve() accordingly.
We need to output the count.
Let's test second example: a=[1,2,3,4]; b=[10,11,12,13,14]. Check integer ratios: 1: 10/1=10, 11/1=11, 12/1=12,13/1=13,14/1=14 -> all integers; max=14? But need also check other a's: 2: 10/2=5,12/2=6,14/2=7; 3: 12/3=4,? 15? no; 4: 12/4=3,? etc. So maximum integer ratio from all pairs is 14 (from a=1,b=14). That gives count=1. Output 1 matches.
Thus solution.
We'll write code.
Potential pitfalls: Use integer division, ensure we don't do floating.
That's it.
But the problem statement uses fraction image maybe representing a_i / b_j? But based on known problem and sample, it's b_j / a_i. Actually double-check: In known CF problem 215A "Bicycle Chain": The gear ratio is defined as b_j / a_i. Yes.
Thus answer.
Let's produce final code: read input, compute, print count.
Complexities O(n*m). Since n,m ≤ 50 trivial.
I'll include a function solve() and main call.
Will be done. ```python import sys
def solve() -> None: data = sys.stdin.read().strip().split() if not data: return it = iter(data) n = int(next(it)) a = [int(next(it)) for _ in range(n)] m = int(next(it)) b = [int(next(it)) for _ in range(m)]
max_ratio = 0 count = 0 for ai in a: for bj in b: if bj % ai == 0: ratio = bj // ai if ratio > max_ratio: max_ratio = ratio count = 1 elif ratio == max_ratio: count += 1 print(count)if name == "main": solve()