It is known that in the classical, 3 dimensional space the vectors are given with (x,y,z) coordinates, which are sometimes called (e.g. in the case of furniture-shopping) width, height, depth. In a galaxy far-far away, in the land of 1 billion dimension the inhabitants of the planet follow a similar system to give vectors, however instead of 3 coordinates, they are using 1 billion (so a vector is of the shape (x₁,x₂,x₃,...,x_1000000000)). Luckily do to the interaction between the gravitational field of the planet and the magical force field which tries to counter it each vector contains a suspiciously high number of direct repetitions, thus the inhabitants usually use the so-called compressed-form of the vectors, which has the following shape: (occurrence₁ value₁ occurrence₂ value₂ ... occurrence_n value_n), where the occurrence gives how many times do we need to write down (consecutively) the following value. For example the vector (1 1 1 ... (total of 100 1s) 2 3 3 4 4 4 ... (total of 999999897 4s) has the compressed form (100 1 1 2 2 3 999999897 4) (so 100 1s, 1 2s, 2 3s, and 999999897 4s). Your task is to calculate the scalar product of two vectors which are given in compressed form (a scalar product of two vectors are the sum of the product of each corresponding coordinate, so in the case of (x,y,z) and (u,v,w) the product is x*u + y*v + z*w).

The input contains two lines, each describing a compressed vector. Each "unit" in a vector is separated by a single space character and to make parsing easier we did not put brackets at the start and end of the vectors. The length of each row is at most 10000 characters.

The output is a single number which is the scalar product of the two given vectors.

• The coordinates of the vectors are integers;
• The number of occurrences of each coordinate is a non-negative integer;
• The absolute value of each intermediate calculation and the final result is at most 2⁴⁰.

Input:

1. 500000001 1 499999999 -1
2. 1000000000 1
3.     

download as text file Output:

1. 2
2.     

download as text file

The first vector in uncompressed form consists of 500 million + 1 number of 1s and then 499999999 number of -1s. The second vector has 1 billion 1-s. Thus the scalar product is 500000001*(1*1) + 499999999*(-1*1) = 2.