Lanhf và FireGhost đi mua sắm ở một cửa hàng ma thuật. Cửa hàng có ~n~ món đồ được đánh số từ ~1~ đến ~n~, món đồ thứ ~i~ có độ hấp dẫn là ~c_i~ và giá tiền là ~v_i~.
Hai người họ muốn mua một bộ sưu tập các món đồ, nhưng với một điều kiện kì lạ. Gọi ~S=\{s_1,s_2,\ldots,s_p\}~ (~1\le s_i\le n~) là bộ sưu tập họ đã mua:
Với mọi ~T=\{t_1,t_2,\ldots,t_q\}~ là một tập con khác rỗng của ~S~, ta có ~c_{t_1}\oplus c_{t_2}\oplus\ldots\oplus c_{t_q}\ne 0~. Ở đây ~\oplus~ chỉ phép thao tác bit XOR.
Tập ~S~ có lực lượng lớn nhất trong tất cả các tập thoả mãn điều kiện trên.
Có thể có rất nhiều bộ sưu tập thoả mãn, tuy nhiên Lanhf thích tập ~A~ còn FireGhost thích tập ~B~. Để thuyết phục FireGhost chọn tập ~A~, Lanhf quyết định thay đổi giá tiền của các món đồ. Cụ thể, với mỗi món đồ ~i~ cậu ta có thể tiêu hao ~(x-v_i)^2~ mana để thay đổi giá tiền của nó thành một số nguyên không âm ~x~. Mối món đồ chỉ có thể bị thay đổi giá trị tối đa ~1~ lần.
Lanhf mong rằng có thể thay đổi giá tiền sao cho tập ~A~ trở thành tập có giá tiền nhỏ nhất và tập ~B~ trở thành tập có giá tiền lớn nhất trong tất cả các bộ sưu tập thoả mãn (giá tiền của bộ sưu tập là tổng giá tiền các món đồ ở trong nó). Hãy giúp Lanhf thực hiện mong muốn của mình với lượng mana tiêu hao ít nhất.
Input
Dòng đầu tiên gồm hai số nguyên ~n~ và ~p~ (~1\le p\le n\le 1000~, ~p\le 64~) — số món đồ trong cửa hàng và kích thước của tập ~A~ và ~B~.
Dòng thứ hai gồm ~n~ số nguyên ~c_1,c_2,\ldots,c_n~ (~1\le c_i<2^{64}~) — độ hấp dẫn của các món đồ.
Dòng thứ ba gồm ~n~ số nguyên ~v_1,v_2,\ldots,v_n~ (~0\le v_i\le 10^6~) — giá tiền của các món đồ.
Dòng thứ tư gồm ~p~ số nguyên phân biệt ~a_1,a_2,\ldots,a_p~ (~1\le a_i\le n~) — các phần tử của tập ~A~.
Dòng thứ năm gồm ~p~ số nguyên phân biệt ~b_1,b_2,\ldots,b_p~ (~1\le b_i\le n~) — các phần tử của tập ~B~.
Dữ liệu đảm bảo ~A~ và ~B~ là hai bộ sưu tập hợp lệ.
Output
In ra một số nguyên là lượng mana ít nhất mà Lanhf cần dùng dể đạt được mong muốn.
Scoring
Subtask ~1~ (~15~ điểm): ~n\le 10~, ~p\le 4~, ~1\le v_i\le 5~.
Subtask ~2~ (~15~ điểm): ~n\le 50~, ~p\le 2~, ~1\le v_i\le 10~.
Subtask ~3~ (~20~ điểm): ~n\le 500~, ~p\le 30~, ~0\le v_i\le 1~.
Subtask ~4~ (~10~ điểm): Hai tập ~A~ và ~B~ trùng nhau.
Subtask ~5~ (~40~ điểm): Không có ràng buộc gì thêm.
Sample Input 1
5 3
1 2 5 6 7
4 4 2 1 3
1 2 3
2 4 5
Sample Output 1
6
Notes
Ở test ví dụ trên, các bộ sưu tập hợp lệ là ~\{1,2,3\}~, ~\{1,2,4\}~, ~\{1,2,5\}~, ~\{1,3,4\}~, ~\{1,3,5\}~, ~\{2,3,4\}~, ~\{2,4,5\}~, ~\{3,4,5\}~. Phương án tối ưu sẽ thay đổi: ~v_3 = 2~, ~v_1 = v_2 = v_4 = v_5 = 3~.
Bình luận