Нещодавно Вася придбав нову шафу-купе. Виявилося, що в ній рівно N однакових секцій та M дверей, розташованих у 2 ряди. Кожні двері збігаються за розміром із секцією, тобто одні двері закривають рівно одну секцію. Це здалося Васі дуже дивним, і він задався ще більш дивним питанням: «Скільки потрібно зробити дій, щоб усі заповнені секції були закриті, а інші – відкриті?». За одну дію Вася може посунути будь-яку з дверей уліво чи вправо на 1 секцію, якщо відповідна позиція в даному ряді вільна. Секція вважається закритою, якщо її закриває щонайменше одна з дверей, та відкритою в іншому випадку.

Завдання

Напишіть програму, яка за початковим розміщенням дверей і за даними про те, які з секцій заповнені, знайде мінімальну кількість дій, за яку Вася зможе зробити всі заповнені секції закритими, а інші – відкритими.

Вхідні дані

У першому рядку вхідних даних записано єдине натуральне число P (P ≤ 3) – кількість наборів вхідних даних. Кожен із наборів задано чотирма рядками. У першому з них записані 2 числа N та M (1 ≤ N ≤ 200, 0 ≤ M ≤ 2N) – кількість секцій і кількість дверей відповідно. У наступних двох рядках записано по N чисел, кожне з яких означає, чи присутні двері на даній позиції (0 – ні, 1 – так). В останньому для даного набору рядку знаходяться N чисел, кожне з яких означає, чи заповнена відповідна секція (0 – ні, 1 – так).

Вихідні дані

Вивести P чисел – мінімальну кількість дій Васі для кожного з наборів вхідних даних. Якщо в окремому наборі цільового розташування досягти неможливо, то для цього набору виведіть -1.

Оцінювання

Додатково виконуються такі умови:

1. 25% тестів: N ≤ 5

2. 15% тестів: у другому ряді немає дверей

3. 25% тестів: N ≤ 50, у другому ряді максимум двоє дверей

4. 75% тестів: N ≤ 50