Trò chơi Đấu Trường Chân Lý do VNGGames phát hành đạt giải thưởng Game của năm tại đêm trao giải Vietnam Game Awards 2024.

Để ăn mừng cho những thành công đạt được, VNGGames tổ chức các trò chơi giải trí cho thành viên trong team. Ban Tổ Chức sẽ giao nhiệm vụ cho các đội chơi, mỗi đội chơi gồm 2 người. Nhiệm vụ cụ thể như sau:

Có ~n~ nhiệm vụ, được đánh số từ ~1~ đến ~n~. Nhiệm vụ ~i~ thuộc loại ~t[i]~.

• Nếu nhiệm vụ ~i~ được giao cho người đã hoàn thành nhiệm vụ ngay trước đó cùng loại thì thời gian thực hiện là ~b[t[i]]~.
• Nếu không, thời gian thực hiện là ~a[t[i]]~.

Mục tiêu của đội chơi là phân chia công việc sao cho phải hoàn thành tất cả nhiệm vụ trong thời gian sớm nhất. Các bạn hãy tính toán xem thời gian tốt nhất để một đội chơi có thể hoàn thành tất cả nhiệm vụ là bao nhiêu.

Lưu ý:

• Nhiệm vụ phải được hoàn thành theo thứ tự đề cho.
• Trong quá trình thực hiện nhiệm vụ, không ai được nghỉ quá ~d~ nhiệm vụ liên tiếp.
• Mỗi nhiệm vụ chỉ cần một trong hai người hoàn thành.

Input

Gồm nhiều test cases. Dòng đầu tiên là một số nguyên ~T~, số lượng test cases ~(T \le 10)~.
Dòng đầu tiên của mỗi test case là ~n, k~ và ~d~ ~(1 \le n, k, d \le 5000)~ lần lượt là số nhiệm vụ, số loại nhiệm vụ và khoảng nghỉ tối đa của một người.
Dòng thứ ~2~ trong mỗi test case là ~n~ số nguyên ~t_1,t_2,\cdots,t_n~ ~(1\le t_i \le k)~ là loại của nhiệm vụ thứ i.
Dòng thứ ~3~ trong mỗi test case là ~k~ số nguyên ~a_1,a_2,\cdots,a_k~ ~(1\le a_i \le 10^9)~ là thời gian để người đó hoàn thành công việc loại ~i~ trong trường hợp thứ 2.
Dòng thứ ~4~ trong mỗi test case là ~k~ số nguyên ~b_1,b_2,\cdots,b_k~ ~(1\le b_i \le a_i)~ là thời gian để người đó hoàn thành công việc loại ~i~ trong trường hợp đầu tiên.

Output

Mỗi dữ liệu được ghi trên một dòng là thời gian ngắn nhất mà một đội chơi có thể hoàn thành xong nhiệm vụ của mình.

Sample Input

1
4 3 4
1 3 1 3 
4 7 8 
2 7 7 

Sample Output

21

Subtask

• ~20\%~ số test có ~n \le 20, T = 1~.
• ~50\%~ số test tiếp theo có ~d = n~.
• ~30\%~ giới hạn đề bài.

Giải thích

2 người ~A~ và ~B~ sẽ làm thứ tự như sau: ~ABAB~ thì thời gian để hoàn thành là: ~4 + 8 + 2 + 7 = 21~.