Robot giao hàng

Pick-E là một robot giao hàng thông minh được phát triển bởi công ty FutureTech. Nó được lập trình để thu thập các gói hàng đặc biệt được đặt rải rác trên một tuyến đường thẳng, tuyến đường này được chia theo mét và được đánh số liên tiếp từ \(0\) trở đi.

Ban đầu, Pick-E đứng tại vị trí \(0\). Trên tuyến đường có \(N\) gói hàng cần thu thập. Gói hàng thứ \(i\) được đặt tại vị trí \(P_i\) và có nhãn màu \(A_i\), cho biết loại mặt hàng trong đó.

Để thu thập một gói hàng, Pick-E cần được trang bị đúng loại bộ kẹp tương ứng với nhãn màu của gói đó. Pick-E chỉ có thể thay đổi bộ kẹp khi nó đang đứng tại điểm \(0\). Tại một thời điểm Pick-E chỉ có thể nhặt một gói hàng nếu nó đứng đúng tại vị trí của gói đó và đang trang bị đúng loại bộ kẹp phù hợp với màu.

Công ty yêu cầu Pick-E phải thu thập đúng \(K\) gói hàng. Mỗi mét Pick-E di chuyển (sang trái hoặc phải) tốn đúng \(1\) giây, và việc nhặt hàng cũng như thay bộ kẹp đều không mất thời gian.

Yêu cầu: Hãy tính thời gian ít nhất để Pick-E có thể thu thập \(K\) gói hàng. Lưu ý Pick-E không cần phải quay trở lại vị trí ban đầu.

Input

Dòng đầu tiên ghi duy nhất một số nguyên \(T \leq 5\) là số lượng test.

Mỗi test gồm:

• Dòng một chứa hai số nguyên dương \(N\) và \(K\) (\(K \leq N \leq 1000\)).
• Dòng thứ hai chứa \(N\) số nguyên dương, số thứ \(i\) là \(P_i\) (\(P_i \leq 10^5\)).
• Dòng thứ ba chứa \(N\) số nguyên dương, số thứ \(i\) là \(A_i\) (\(A_i \leq 1000\)).

Output

Với mỗi test, in ra thời gian ít nhất mà Pick-E cần để thu thập đủ \(K\) gói hàng.

Example

1
4 3
1 2 3 4
1 8 1 8

6

Scoring

• Subtask 1 (15 điểm): \(N \le 10\).
• Subtask 2 (25 điểm): \(N \le 50\).
• Subtask 3 (60 điểm): \(N \leq 1000\).