Alice và Bob cùng chơi một trò chơi trên dãy số nguyên. Alice luôn muốn nhanh chóng tìm được một đoạn gồm các phần tử liên tiếp mà khi tính AND ~(\&)~ của các phần tử đó bằng ~0~. Bob thì tìm cách thay đổi các số để làm khó Alice. Cụ thể, Bob muốn nhờ bạn lập trình giải bài toán sau:

Cho số nguyên ~k~ (~1 \le k \le n~) và hai dãy số ~a~ và ~c~ có cùng độ dài ~n~. Với mỗi vị trí ~i~ (~1 \le i \le n~) ta có thể thay đổi ~a_i~ thành giá trị bất kì với chi phí là ~c_i~. Tìm tổng chi phí nhỏ nhất để thay đổi dãy ~a~ sao cho ~a_i \& a_{i+1} \&...\&a_{i+k-1} = 0~ với mọi ~1 \le i \le n-k+1~.

Nhắc lại, phép toán AND (có kí hiệu là ~\&~) được định nghĩa như sau: Kết quả của phép toán AND giữa 2 số nguyên không âm ~x~ và ~y~ là một số nguyên không âm ~z~ trong đó bit thứ ~i~ trong biểu diễn nhị phân của ~z~ sẽ là ~1~ khi và chỉ khi bit thứ ~i~ trong biểu diễn nhị phân của ~x~ và ~y~ đồng thời bằng ~1~, ngược lại bit thứ ~i~ trong biểu diễn nhị phân của ~z~ sẽ là ~0~

Dữ liệu vào

Dòng đầu tiên là một số nguyên ~t~ ~(1 \le t \le 10^{6})~ cho biết số bộ dữ liệu, tiếp theo mỗi bộ dữ liệu có khuôn dạng:

• Dòng dầu tiên gồm hai số nguyên ~n, k~ ~(1 \le k \le n \le 10^{6})~
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2,..., a_n~ ~(0 \le a_i \le 2^{30})~
• Dòng cuối cùng gồm ~n~ số nguyên ~c_1, c_2,..., c_n~ ~(0 \le c_i \le 2^{30})~

Kết quả ra

• Ghi ra thiết bị chuẩn gồm ~t~ dòng, mỗi dòng tương ứng là tổng chi phí nhỏ nhất tìm được của bộ dữ liệu xuất hiện trong dữ liệu vào

Ràng buộc

• Subtask 1 (20 điểm): Tổng các giá trị của ~n~ trong ~t~ bộ dữ liệu trong vượt quá ~20~
• Subtask 2 (20 điểm): ~c_i \le 1~ với mọi ~1 \le i \le n~
• Subtask 3 (30 điểm): Tổng các giá trị của ~n~ trong ~t~ bộ dữ liệu trong vượt quá ~5000~
• Subtask 4 (30 điểm): Không có ràng buộc gì thêm

Ví dụ

Dữ liệu

1
5 2
1 2 3 2 1
3 2 5 2 3

Kết quả

4