Benny

Benny là một nhà nghiên cứu động vật và cần đi quan sát \(K\) con chó. Benny sống trên một con đường nằm ngang được đánh dấu theo từng mét với các số liên tiếp \(0, 1, 2, 3, ...\). Benny bắt đầu trong nhà của mình, ở vị trí 0. Có \(N\) con chó trên đường phố. Con chó thứ \(i\) cách nhà Benny trên phố \(P_i\) mét phía bên phải (có thể có nhiều hơn một con chó ở cùng một vị trí).

Các con chó có nhiều màu khác nhau, được biểu thị bằng các số nguyên dương. Con thứ \(i\) có màu \(A_i\).

Nếu Benny đang ở nhà, cô ấy có thể thay đổi màu áo hiện tại của mình. Điều này rất quan trọng vì các con chó rất nhút nhát! Benny chỉ có thể quan sát một con chó nếu cô ấy ở cùng vị trí với con chó đó và mặc áo cùng màu với nó.

Benny mất một giây để di chuyển một mét sang trái hoặc phải trên đường phố. Cô ấy không mất thời gian để thay áo sơ mi hoặc quan sát một con chó.

Yêu cầu: Hãy tính xem Benny cần thời gian ít nhất để quan sát cả \(K\) con chó là bao lâu? Lưu ý rằng cô ấy không cần phải trở về nhà sau khi quan sát xong \(K\) con chó.

Input

Dòng đầu tiên ghi duy nhất một số nguyên \(T\leq 5\) là số lượng trường hợp test. Mỗi nhóm dòng trong số \(T\) nhóm dòng sau bao gồm:

• Dòng một chứa hai số nguyên dương \(N\) và \(K\) ($ K \leq N \leq 1000$) tương ứng là số lượng con chó trên đường phố và số lượng con chó mà Benny cần quan sát.

• 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

• Ghi ra \(T\) dòng, mỗi dòng ghi một số là thời gian tối thiểu để Benny quan sát hết \(K\) con chó.

Example

1
4 3
1 2 3 4
1 8 1 8

6

Scoring

• Subtask 1: \(N \leq 50\).

• Subtask 2: \(N \leq 1000\).