Shichikuji must supply electricity to ~n~ cities. City ~i~ sits at coordinates ~(x_i, y_i)~.

A city has electricity if it has a power station, or if it is connected (directly or through other cities) to a city that does.

• Building a power station in city ~i~ costs ~c_i~.
• Connecting cities ~i~ and ~j~ with a wire costs ~(k_i + k_j) \cdot (|x_i - x_j| + |y_i - y_j|)~.

Wires run along cardinal directions, so their length is the Manhattan distance between the two cities. Find the minimum cost to give every city electricity.

Input

The first line contains an integer ~n~.

The next ~n~ lines each contain two integers ~x_i~ and ~y_i~.

The next line contains ~n~ integers ~c_1, c_2, \ldots, c_n~.

The last line contains ~n~ integers ~k_1, k_2, \ldots, k_n~.

Output

Output a single integer: the minimum cost.

Constraints

• ~1 \le n \le 2000~
• ~1 \le x_i, y_i \le 10^6~
• ~1 \le c_i, k_i \le 10^9~

Example 1

Input

3
2 3
1 1
3 2
3 2 3
3 2 3

Output

8

Explanation

Building a station in every city costs ~3 + 2 + 3 = 8~, which is optimal.

Example 2

Input

3
2 1
1 2
3 3
23 2 23
3 2 3

Output

27

Explanation

Build a station in city ~2~ (cost ~2~), connect ~1~--~2~ (cost ~10~), and connect ~2~--~3~ (cost ~15~), for a total of ~27~.