Inosuke and Trailing Zero

shimul12614 DIU Take-Off Programming...
Limits 1s, 512 MB

Inosuke and Tanziro are overjoyed because Mr.Haganezuka is bringing their sword of revenge. Because they broke their old sword while trying to kill Spider Demons. After receiving the new sword, Inosuke begins to break it again to give shape like his old one, which angers Mr.Haganezuka because he cannot bear that his creation is being destroyed. He raged at Inosuke. After Tanjiro tried for a long time finally, he calmed down. But for this crime, however, he punished Inosuke with a mathematical problem because he knew that Inosuke was very weak in mathematics.

Mr.Haganezuka gave him an array AA with NN integers and another array BB with MM integers. Inusoke has to do the following operation on these arrays-

  1. Multiply all the integers of the array AA, resA=(A1×A2×A3××An)resA = (A_1 \times A_2 \times A_3 \times … \times A_n)

  2. Multiply all the integers of the array BB, resB=(B1×B2×B3××Bm)resB= (B_1 \times B_2 \times B_3 \times … \times B_m)

  3. Then determine how many trailing zeros are there in resAresB\frac{resA}{resB}

Mr.Haganezuka doesn't like fractional numbers. So he will always give numbers of the array such a way that resAresA is always divisible by resBresB.

Input

First line of input contains two integers nn and mm. (1n+m105)(1\leq n + m\leq 10^{5})

Second line contains nn integers (A1,A2,A3,,An).(1Ai109)(A_1, A_2, A_3, … ,A_n).(1 \leq A_i \leq10^{9})

Third line contains mm integers (B1,B2,B3,Bm)(1Bi109)(B_1, B_2, B_3, … B_m) (1 \leq B_i \leq10^{9})

Output

Number of trailing zero in the product of all integers of AA divided by product of all integers in BB.

Sample

InputOutput
1 2
1000
2 5
2

Submit

Login to submit.

Statistics

58% Solution Ratio
n3wb13_223Earliest, Apr '21
Zihad_BdFastest, 0.0s
Ahamed210Lightest, 131 kB
steinumShortest, 365B
Toph uses cookies. By continuing you agree to our Cookie Policy.