Шкаф-купе
Недавно Вася приобрел новый шкаф-купе. В шкафу ровно N одинаковых секций и M дверей, расположенных в 2 ряда. Каждая дверь соответствует по размеру одной секции, то есть одна дверь закрывает ровно одну секцию. Это показалось Васе очень странным, и он задался ещё более странным вопросом: «Сколько нужно сделать действий, чтобы все заполненные секции были закрыты, а остальные – открыты?». За одно действие Вася может сдвинуть любую из дверей влево или вправо на 1 секцию, если соответствующая позиция в данном ряду свободна. Секция считается закрытой, если её закрывает хотя бы одна из дверей, и открытой в противном случае.
Задание
Напишите программу, которая по начальному размещению дверей и данным о том, какие из секций заполнены, найдёт минимальное количество действий, за которое Вася сможет сделать все заполненные секции закрытыми, а остальные – открытыми.
Входные данные
В первой строке входных данных записано единственное натуральное число P (P ≤ 3) – количество наборов входных данных. Каждый из наборов задан четырьмя строками. В первой из них записаны 2 числа N и M (1 ≤ N ≤ 200, 0 ≤ M ≤ 2N) – количество секций и количество дверей соответственно. В следующих двух строках записано по N чисел, каждое из которых означает, присутствуют ли двери на данной позиции (0 – нет, 1 – да). В последней для данного набора строке находятся N чисел, каждое из которых означает, заполнена ли соответствующая секция (0 – нет, 1 – да).
Выходные данные
Выведите P чисел – минимальное количество действий Васи для каждого из наборов входных данных. Если в отдельном наборе целевого расположения достичь невозможно, то для этого набора выведите -1.
Примеры
Оценивание
Дополнительно выполняются такие условия:
25% тестов: N ≤ 5
15% тестов: во втором ряду нет дверей
25% тестов: N ≤ 50, во втором ряду максимум двое дверей
75% тестов: N ≤ 50