Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Inosuke and Trailing Zero

By shimul12614 · 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

    Discussion

    Statistics


    55% Solution Ratio

    n3wb13_223Earliest, 6d ago

    showrov_couFastest, 0.0s

    Ahamed210Lightest, 131 kB

    steinumShortest, 365B

    Submit

    Login to submit