P6621 [Joint NOI Qualifier 2020 Paper A] Magic Shop

1 s, 512 MB.

Lili and Lunlun came to a magic shop. There are $n$ gifts in the shop, numbered from $1$ to $n$. Gift $i$ has charm value $c_i$ and price $v_i$. They want to buy some gifts, but their requirement is strange. Suppose the set of gifts they buy is $S=\{s_1,s_2,\dots,s_p\}(1\leq s_i\leq 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$ is non-zero, i.e., $c_{t_1} \oplus c_{t_2} \oplus \cdots \oplus c_{t_q} \neq 0$. Here, $\oplus$ denotes the XOR operation. On top of this, they also want the number of gifts they buy to be as large as possible. For example, let $c_1=1,c_2=2,c_3=5,c_4=6,c_5=7$. Then $S_1=\{2,3,5\}$ does not satisfy the requirement, because $c_2 \oplus c_3 \oplus c_5=0$. Sets $S_2=\{1,2,3\}$ and $S_3=\{2,4,5\}$ satisfy the requirement: every non-empty subset has a non-zero XOR sum. Set $S_4=\{1,2\}$ is not valid because the number of gifts it contains is not maximal. There may be many gift sets that satisfy their requirement, so the shop owner picked two such sets $A$ and $B$ for them (obviously they contain the same number of gifts). Lunlun likes set $A$, but Lili prefers set $B$. To make Lili agree to buy set $A$, Lunlun decides to use magic to change gift prices. More specifically, Lunlun can spend $(x-v_i)^2$ magic power to change the price of gift $i$ to any integer $x$. Each gift’s price can be changed at most once. Lunlun wants that after changing prices, $A$ is the set with the minimum total price among all gift sets that satisfy the requirement, and $B$ is the set with the maximum total price among all such gift sets (the total price of a set is the sum of the prices of all gifts it contains). Please help Lunlun compute the minimum magic power he must spend to achieve his goal.

The first line contains two integers $n, m$, representing the total number of gifts and the number of gifts contained in set $A(B)$, respectively. The second line contains $n$ integers $c_i$, where the $i$-th integer is the charm value of gift $i$. The third line contains $n$ integers $v_i$, where the $i$-th integer is the price of gift $i$. The fourth line contains $m$ integers $a_i$, representing the indices of gifts in set $A$. The data guarantees that all $a_i$ are pairwise distinct. The fifth line contains $m$ integers $b_i$, representing the indices of gifts in set $B$. The data guarantees that all $b_i$ are pairwise distinct. The data guarantees $1 \leq a_i, b_i \leq n$, and both sets $A$ and $B$ satisfy their requirement.

Output one integer in a single line, representing the minimum magic power Lunlun needs to spend.

#### Sample 1 Explanation 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\}$. One optimal repricing plan is: $c_1=c_2=c_4=c_5=3$, $c_3=2$. #### Sample 2 See the attached files `shop2.in` and `shop2.ans`. #### Sample 3 See the attached files `shop3.in` and `shop3.ans`. #### Constraints For all testdata: $1\leq n\leq 1000$, $1\leq m\leq 64$, $1\leq c_i < 2^{64}$, $0\leq v_i\leq 10^6$. The specific limits for each test point are shown in the table below: | Test Point ID | $n \leq$ | $m \leq$ | Special Constraint | | :----------: | :----------: | :----------: | :----------: | | $1 \sim 3$ | $10$ | $4$ | $1 \leq v_i \leq 5$ | | $4 \sim 6$ | $50$ | $2$ | $1 \leq v_i \leq 10$ | | $7 \sim 10$ | $500$ | $30$ | $0 \leq v_i \leq 1$ | | $11 \sim 12$ | $1000$ | $64$ | $A$ and $B$ are the same | | $13 \sim 20$ | $1000$ | $64$ | None | Translated by ChatGPT 5