Şkaf-kupe

Vasya yeni bir dolab alıb və bu dolabda tam olaraq N eyni bölmə və M qapı var. Bu bölmələr və qapılar iki sırada yerləşir. Hər bir qapı bir bölməni tam örtəcək ölçüdədir. Vasya bu vəziyyəti qəribə hesab etdi və belə bir sual verdi: "Bütün dolu bölmələrin örtülü, digərlərinin isə açıq olması üçün neçə hərəkət lazımdır?" Vasya hər bir hərəkətlə istənilən qapını sola və ya sağa 1 bölmə qədər sürüşdürə bilər, əgər həmin sırada uyğun mövqe boşdursa. Bir bölmə örtülü sayılır, əgər onu ən azı bir qapı örtürsə, əks halda açıq sayılır.

Tapşırıq

Başlanğıc qapı yerləşməsinə və hansı bölmələrin dolu olduğuna dair məlumatlara əsaslanaraq, Vasya'nın bütün dolu bölmələri örtülü, digərlərini isə açıq etmək üçün minimal hərəkət sayını tapacaq bir proqram yazın.

Giriş məlumatları

Giriş məlumatlarının birinci sətirində tək bir natural ədəd P (P ≤ 3) – giriş məlumat dəstlərinin sayı verilir. Hər bir dəst dörd sətirdən ibarətdir. Birinci sətirdə 2 ədəd N və M (1 ≤ N ≤ 200, 0 ≤ M ≤ 2N) – bölmələrin və qapıların sayı verilir. Növbəti iki sətirdə hər biri N ədəd olmaqla, həmin mövqedə qapının olub-olmamasını göstərən ədədlər (0 – yox, 1 – bəli) verilir. Sonuncu sətirdə isə hər bir dəst üçün uyğun bölmənin dolu olub-olmamasını göstərən ədədlər (0 – yox, 1 – bəli) verilir.

Çıxış məlumatları

Hər bir giriş məlumat dəsti üçün Vasya'nın minimal hərəkət sayını göstərən P ədəd çıxarın. Əgər müəyyən bir dəst üçün məqsədli yerləşməyə nail olmaq mümkün deyilsə, həmin dəst üçün -1 çıxarın.

Nümunələr

Qiymətləndirmə

Əlavə olaraq aşağıdakı şərtlər yerinə yetirilir:

1. 25% testlər: N ≤ 5

2. 15% testlər: ikinci sırada qapı yoxdur

3. 25% testlər: N ≤ 50, ikinci sırada maksimum iki qapı var

4. 75% testlər: N ≤ 50