Lili and Lunlun have come to a magic shop. There are $n$ gifts in the shop, numbered $1$ to $n$. The $i$-th gift has a charm value $c_i$ and a price $v_i$.

They wish to purchase some gifts, but they have a peculiar requirement: suppose the set of purchased gifts is $S = \{s_1, s_2, \dots, s_p\}$ ($1\le s_i\le n$). They require that for any non-empty subset $T = \{t_1, t_2, \dots, t_q\}$ of $S$, the XOR sum of the charm values of all gifts in $T$ must not be zero, i.e., $c_{t_1} \oplus c_{t_2} \oplus \cdots \oplus c_{t_q} \neq 0$, where $\oplus$ denotes the XOR operation. Furthermore, they want to maximize the number of gifts purchased.

For example, if $c_1 = 1, c_2 = 2, c_3 = 5, c_4 = 6, c_5 = 7$, then $S_1 = \{2,3,5\}$ does not meet the requirement because $c_2 \oplus c_3 \oplus c_5 = 0$. $S_2 = \{1,2,3\}$ and $S_3 = \{2, 4, 5\}$ meet the requirement, as the XOR sum of any of their non-empty subsets is non-zero. $S_4 = \{1, 2\}$ is not valid because it does not contain the maximum possible number of gifts.

There may be many gift sets that satisfy their requirements. The shopkeeper has selected two such sets, $A$ and $B$ (which obviously contain the same number of gifts). Lunlun likes set $A$, but Lili prefers set $B$. To convince Lili to agree to purchase set $A$, Lunlun decides to use magic to change the prices of the gifts. Specifically, Lunlun can spend $(x - v_i)^2$ magic points to change the price of the $i$-th gift to any integer $x$. Each gift can have its price changed at most once.

Lunlun wants to ensure that after the price changes, $A$ is the set with the minimum total price among all valid gift sets, and $B$ is the set with the maximum total price among all valid gift sets (the total price of a gift set is the sum of the prices of all gifts it contains). Please help Lunlun calculate the minimum magic points he needs to spend to achieve his goal.

Input

The first line contains two integers $n$ and $m$, representing the total number of gifts and the number of gifts in set $A$ (and $B$), respectively.

The second line contains $n$ integers $c_i$, where the $i$-th integer is the charm value of the $i$-th gift.

The third line contains $n$ integers $v_i$, where the $i$-th integer is the price of the $i$-th gift.

The fourth line contains $m$ integers $a_i$, representing the indices of the gifts in set $A$. It is guaranteed that all $a_i$ are distinct.

The fifth line contains $m$ integers $b_i$, representing the indices of the gifts in set $B$. It is guaranteed that all $b_i$ are distinct.

It is guaranteed that $1\le a_i, b_i \le n$, and both gift sets $A$ and $B$ satisfy the requirements.

Output

Output a single integer representing the minimum magic points Lunlun needs to spend.

Examples

Input 1

5 3
1 2 5 6 7
4 4 2 1 3
1 2 3
2 4 5

Output 1

6

Note 1

The valid gift sets are: $\{1,2,3\},\{1,2,4\},\{1,2,5\},\{1,3,4\},\{1,3,5\},\{2,3,4\},\{2,4,5\},\{3,4,5\}$.

An optimal price adjustment scheme is: $c_1 = c_2 = c_4 = c_5 = 3, c_3 = 2$.

Input 2

See the provided files.

Input 3

See the provided files.

Subtasks

For all test data: $1\le n\le 1000$, $1\le m\le 64$, $1\le c_i < 2^{64}$, $0\le v_i\le 10^6$.

The specific constraints for each test point are shown in the table below: