Zero-indexed arrays A and B consisting of N non-negative integers are given. Together, they represent N real numbers, denoted as C[0], ..., C[N−1]. Elements of A represent the integer parts and the corresponding elements of B (divided by 1,000,000) represent the fractional parts of the elements of C. More formally, A[I] and B[I] represent C[I] = A[I] + B[I] / 1,000,000.

For example, consider the following arrays A and B:

`A[0] = 0 B[0] = 500,000 A[1] = 1 B[1] = 500,000 A[2] = 2 B[2] = 0 A[3] = 2 B[3] = 0 A[4] = 3 B[4] = 0 A[5] = 5 B[5] = 20,000`

They represent the following real numbers:

`C[0] = 0.5 C[1] = 1.5 C[2] = 2.0 C[3] = 2.0 C[4] = 3.0 C[5] = 5.02`

A pair of indices (P, Q) is

*multiplicative*if 0 ≤ P < Q < N and C[P] * C[Q] ≥ C[P] + C[Q].
The above arrays yield the following multiplicative pairs:

- (1, 4), because 1.5 * 3.0 = 4.5 ≥ 4.5 = 1.5 + 3.0,
- (1, 5), because 1.5 * 5.02 = 7.53 ≥ 6.52 = 1.5 + 5.02,
- (2, 3), because 2.0 * 2.0 = 4.0 ≥ 4.0 = 2.0 + 2.0,
- (2, 4) and (3, 4), because 2.0 * 3.0 = 6.0 ≥ 5.0 = 2.0 + 3.0.
- (2, 5) and (3, 5), because 2.0 * 5.02 = 10.04 ≥ 7.02 = 2.0 + 5.02.
- (4, 5), because 3.0 * 5.02 = 15.06 ≥ 8.02 = 3.0 + 5.02.

Write a function:

int solution(int A[], int B[], int N);

that, given zero-indexed arrays A and B, each containing N non-negative integers, returns the number of multiplicative pairs of indices.

If the number of multiplicative pairs is greater than 1,000,000,000, the function should return 1,000,000,000.

For example, given:

`A[0] = 0 B[0] = 500,000 A[1] = 1 B[1] = 500,000 A[2] = 2 B[2] = 0 A[3] = 2 B[3] = 0 A[4] = 3 B[4] = 0 A[5] = 5 B[5] = 20,000`

the function should return 8, as explained above.

Assume that:

- N is an integer within the range [0..100,000];
- each element of array A is an integer within the range [0..1,000];
- each element of array B is an integer within the range [0..999,999];
- real numbers created from arrays are sorted in non-decreasing order.

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).