Sparse Dot Product

Two sparse vectors store only non-zero coordinates. Compute their dot product by multiplying values at shared indices and summing the products.

Input

The first line contains n and m (1 ≤ n,m ≤ 200000). The next n lines contain distinct index-value pairs for the first vector; the following m lines describe the second. Indices are positive and at most 10^9; |value| ≤ 10^9.

Output

Print the dot product.

Example 1

Input

3 4
1 5
4 2
10 -3
2 7
4 6
10 2
20 9

Output

6

Example 2

Input

1 1
100 7
100 -2

Output

-14