Dot Product of Two Vectors

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem

Given two integer vectors

$$A=(a_0,\ldots,a_{n-1}),\qquad B=(b_0,\ldots,b_{n-1}),$$

compute their dot product

$$\boxed{A\cdot B=\sum_{i=0}^{n-1}a_i b_i}.$$

Use a 64-bit accumulator.

Input

The first line contains $n$. The second line contains $A$ and the third line contains $B$.

Output

Print the dot product $A\cdot B$.

Subtask

Subtask 1 (20 points): $1\le n\le10$, $|a_i|,|b_i|\le10^3$.

Subtask 2 (30 points): $1\le n\le5000$, $|a_i|,|b_i|\le10^5$.

Subtask 3 (50 points): $1\le n\le2\cdot10^5$, $|a_i|,|b_i|\le10^6$.

Example

Input

4
1 3 -2 5
4 -1 6 2

Output

-1

Explanation

The result follows directly from the mathematical definition above.