Sliding wardrobe

Vasya recently purchased a new sliding wardrobe with exactly N identical sections and M doors, arranged in 2 rows. Each door is the size of a section, meaning one door covers exactly one section. This peculiar setup led Vasya to wonder: "How many moves are required to ensure all filled sections are covered, while the others remain open?" In a single move, Vasya can slide any door left or right by 1 section, provided the adjacent position in that row is unoccupied. A section is considered covered if at least one door is over it, and open otherwise.

Task

Develop a program that, given the initial placement of the doors and the status of each section (filled or not), calculates the minimum number of moves Vasya needs to make all filled sections covered and the others open.

Input

The first line of the input contains a single natural number P (P ≤ 3) – the number of input data sets. Each data set consists of four lines. The first line contains 2 numbers N and M (1 ≤ N ≤ 200, 0 ≤ M ≤ 2N) – the number of sections and the number of doors, respectively. The next two lines each contain N numbers, indicating the presence of a door at each position (0 – no, 1 – yes). The last line for the given set contains N numbers, each indicating whether the corresponding section is filled (0 – no, 1 – yes).

Output

Output P numbers – the minimum number of moves Vasya needs for each set of input data. If achieving the desired arrangement is impossible for a particular set, output -1 for that set.

Evaluation

Additional conditions for the tests are as follows:

1. 25% of tests: N ≤ 5

2. 15% of tests: there are no doors in the second row

3. 25% of tests: N ≤ 50, with at most two doors in the second row

4. 75% of tests: N ≤ 50

Examples