Шафа-купе#7886

Шафа-купе

1 секунда

64 мегабайти

Середня

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

Завдання

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

Вхідні дані

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

Вихідні дані

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

Приклади

Приклад 1

Оцінювання

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

$25%$ тестів: $N \leq 5$ N \leq 5
$15%$ тестів: у другому ряді немає дверей
$25%$ тестів: $N \leq 50$ N \leq 50, у другому ряді максимум двоє дверей
$75%$ тестів: $N \leq 50$ N \leq 50