Background

When everyone is accelerating, you and I met at a crossroads in life at a constant speed.

It was a glance that stirred my heart, yet also a regret that we could not stay. Once again, we run at a constant speed toward our own directions. When will we meet again next time...

Problem Description

There are $n + m$ points on the Cartesian plane, where:

• There are $n$ type $\rm A$ points. Initially, they are located at $(1, 0), (2, 0), (3, 0), \dots, (n, 0)$ in order.
• There are $m$ type $\rm B$ points. Initially, they are located at $(0, 1), (0, 2), (0, 3), \dots, (0, m)$ in order.

At some moment, type $\rm A$ and type $\rm B$ points start moving at the same time. Specifically:

• For the $i$-th type $\rm A$ point, it moves upward (i.e. in the positive direction of the $y$ axis) at a constant speed of $a_i$ units per second. In particular, if $a_i = 0$, then the point stays still forever.
• For the $i$-th type $\rm B$ point, it moves rightward (i.e. in the positive direction of the $x$ axis) at a constant speed of $b_i$ units per second. In particular, if $b_i = 0$, then the point stays still forever.

Meeting and parting are nothing special. As a passer-by in rushing time, at this station where you stay briefly, can you help Little T solve this simple problem: find how many pairs of points will meet at some moment, i.e. they are at the same position at some time.

Since you cannot stop time, all points will keep moving endlessly, whether they meet or not. May you, running on this road, one day meet your ideals at a constant speed, never stopping.

Input Format

The first line contains two positive integers $n, m$.

The second line contains $n$ integers $a_1\dots a_n$, representing the moving speeds of the $1\dots n$-th type $\rm A$ points in order.

The third line contains $m$ integers $b_1\dots b_m$, representing the moving speeds of the $1\dots m$-th type $\rm B$ points in order.

Output Format

One line with one integer, representing how many pairs of points will meet at some moment.

3 3
1 2 3
3 2 1

1

3 3
2 5 1
83 101 98

0

Hint

Sample Explanation 1

When $t = 1$, the $2$-nd type $\rm A$ point and the $2$-nd type $\rm B$ point reach the point $(2, 2)$ at the same time. This is also the only meeting in this sample, so the output is $1$.

Data Scale and Constraints

This problem uses bundled testdata.

• Subtask 0 (10 pts): $n \leq 10$, $m \leq 10$.
• Subtask 1 (20 pts): $n \leq 5\times 10^3$, $m \leq 5\times 10^3$.
• Subtask 2 (30 pts): guaranteed $\forall a_i \geq 1$, $\forall b_i \geq 1$.
• Subtask 3 (40 pts): no special restrictions.

For all testdata, $1 \leq n, m \leq 10^6$, $0 \leq a_i, b_i \leq 10^9$.

Translated by ChatGPT 5