405555: GYM101992 C Array transformation

C. Array transformationtime limit per test7 secondsmemory limit per test1024 megabytesinputtransform.inoutputstandard 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 C_i 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 |A_i|, |B_i|, |C_i| ≤ 10⁹.

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.

ExampleInput

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.