C. Array transformation
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
transform.in
output
standard output

Given two arrays A and B. You need to transform the array A to B by deleting zero or more elements from A. However, you are only allowed to delete an element if it satisfies at least one of the two following conditions:

  • There doesn't exist a non-deleted element to its left with the same value.
  • There doesn't exist a non-deleted element to its right with the same value.
After removing an element which was intitally at position i, a value of Ci will be added to your score. If your score is initially zero, what is the minimum score that you can have after transforming A to B?
Input

The first line of the input is the number of test cases T.

Each test case starts with a line containing two space-seperated integers N and M the length of the array A and the length of the array B respectively, where 1 ≤ M ≤ N ≤ 2000. The following three lines represent arrays A, B and C respectively, where |Ai|, |Bi|, |Ci| ≤ 109.

It's guaranteed that the length of A equals the length of C.

Output

For each test case output a single line containing the minimum score or 'No' without the quotes if you can't transform A to B.

Example
Input
3
6 3
1 2 2 1 2 1
1 2 1
1 100 2 1 -1 50
3 1
1 1 1
1
-100 0 1
2 1
1 1
-2
-100 1
Output
51
-100
No
Note

Here is the explanation of the first test case: You can transform A to B as follows:

  1. Delete '2' at the 5th position and add -1 to your score.
  2. Delete '1' at the 6th position and add 50 to your score.
  3. Delete '2' at the 3rd position and add 2 to you score (we can do this now because we removed all the elements with value 2 to its right).

Note : You couldn't have started by deleting the '2' at the third position as the first operation because it doesn't initially satisfy any of the mentioned conditions.