Diệt rồng

Trong một vương quốc xa xưa, các dũng sĩ được giao nhiệm vụ tiêu diệt những con rồng hung ác đang đe dọa cuộc sống của người dân. Có \(n\) con rồng, mỗi con được đánh số từ \(1\) đến \(n\), và thuộc về loài \(t[i]\).

Khi đối mặt với một con rồng loại \(i\), dũng sĩ có thể mất thời gian khác nhau để tiêu diệt nó tùy thuộc vào kinh nghiệm:

• Nếu con rồng loại \(i\) là loại cuối cùng mà một dũng sĩ vừa tiêu diệt, thì dũng sĩ đó có thể sử dụng kinh nghiệm vừa học được và chỉ cần thời gian \(b[t[i]]\) để tiêu diệt.
• Nếu không, dũng sĩ cần thời gian dài hơn là \(a[t[i]]\) để chiến đấu và tiêu diệt con rồng.

Nhận nhiệm vụ gồm có \(2\) dũng sĩ sẽ phối hợp với nhau để tiêu diệt tất cả các con rồng trong thời gian sớm nhất có thể. Hãy tính toán thời gian tối thiểu cần thiết để hoàn thành nhiệm vụ này.

Lưu ý:

• Các con rồng phải được tiêu diệt theo thứ tự từ \(1\) đến \(n\).
• Trong quá trình chiến đấu, không dũng sĩ nào chọn không chiến đấu quá \(d\) con rồng liên tiếp.
• Mỗi con rồng chỉ có thể được tiêu diệt bởi một dũng sĩ duy nhất.

Input

• Gồm nhiều trận chiến thử thách. Dòng đầu tiên là một số nguyên \(T\), số lượng trận chiến \((T \leq 5)\).
• Dòng đầu tiên của mỗi trận chiến là \(n, k\) và \(d\) \((1 \leq n, k, d \leq 5000)\) lần lượt là số lượng loài rồng, số loại loài rồng và số con rồng liên tiếp không đánh nhiều nhất của một dũng sĩ.
• Dòng thứ 2 trong mỗi trận chiến là \(n\) số nguyên \(t_1, t_2, \dots, t_n\) \((1 \leq t_i \leq k)\) là loại của loài rồng thứ \(i\).
• Dòng thứ 3 trong mỗi trận chiến là \(k\) số nguyên \(a_1, a_2, \dots, a_k\) \((1 \leq a_i \leq 10^9)\) là thời gian để dũng sĩ đó tiêu diệt một loài rồng loại \(i\) trong trường hợp \(2\).
• Dòng thứ 4 trong mỗi trận chiến là \(k\) số nguyên \(b_1, b_2, \dots, b_k\) \((1 \leq b_i \leq a_i)\) là thời gian để dũng sĩ đó tiêu diệt một loài rồng loại \(i\) trong trường hợp \(1\).

Example

1
5 2 2
2 1 2 2 2
2 2
1 1

8

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

21

Scoring

• Có \(20\%\) số test ứng với \(N \leq 20\).
• Có \(30\%\) số test ứng với \(N, K \leq 100\).
• Có \(50\%\) số test còn lại không có ràng buộc gì thêm.