Taxtanın Üstündə Gəzmək
Bir qrup quldur uğurla ticarət gəmisini ələ keçirib. Gəmi ciddi şəkildə zədələndiyi üçün bütün yük quldur gəmisinə köçürülməlidir.
Quldurlar hər iki gəmiyə bir taxta lövhə bağlayıblar. Bu lövhə vasitəsilə quldurlar bir gəmidən digərinə keçə bilərlər, lakin eyni anda yalnız bir quldur keçə bilər.
Hər bir quldur aşağıdakı addımları yerinə yetirir:
Quldur gəmisindən ticarət gəmisinə taxta lövhə ilə keçmək
Yük anbarından bir əşya götürüb taxta lövhəyə qayıtmaq
Əşya ilə birlikdə taxta lövhədən quldur gəmisinə keçmək
Əşyanı yük anbarına qoyub taxta lövhəyə qayıtmaq
Bu dörd addımın hər biri hər bir quldur üçün müəyyən bir vaxt alır. Hər bir quldur bu addımları təkrarlayacaq, ticarət gəmisindəki əşyaların sayı oradakı quldurların sayına bərabər olana qədər (yəni quldurun götürəcəyi heç nə qalmayana qədər).
Əgər quldur taxta lövhəyə çatırsa və o, başqa bir quldur tərəfindən istifadə olunursa, o, taxta lövhənin öz tərəfində gözləyəcək. Taxta lövhə boşaldıqda və taxta lövhənin hər iki tərəfində quldurlar olduqda, ticarət gəmisinin tərəfindəki quldurlar (bir əşya daşıyan) birinci keçəcək. Taxta lövhənin hər iki tərəfində quldurlar növbəyə dururlar, yəni ora birinci çatan birinci keçəcək. Əgər iki və ya daha çox quldur eyni anda taxta lövhənin eyni tərəfinə çatarsa, ən yavaş olan (yəni bu gəmidə yük anbarına gedib-gəlmək üçün ən çox vaxt sərf edən) birinci keçəcək. Sonuncu quldurun son əşya ilə taxta lövhədən keçməsi üçün nə qədər vaxt lazım olduğunu müəyyən edə bilərsinizmi?
Giriş verilənləri
Girişin ilk sətri bir ədəd ehtiva edir: izlənəcək test hallarının sayı. Hər bir test halı aşağıdakı formata malikdir:
Bir sətir iki tam ədəd N və P ilə, 1 ≤ N ≤ 100,000 və 1 ≤ P ≤ 1,000 şərtlərini ödəyir: ticarət gəmisindəki əşyaların sayı və quldurların sayı, müvafiq olaraq.
P sətir, hər biri 4 tam ədəd t_1 ilə t_4 arasında, 1 ≤ t_i ≤ 1,000 şərtlərini ödəyir: bu quldurun hər bir addımı (yuxarıda göstərildiyi kimi) tamamlamaq üçün sərf etdiyi vaxt saniyə ilə.
Başlanğıcda, bütün quldurlar girişdə verilən sıraya uyğun olaraq quldur gəmisində taxta lövhədə növbəyə dururlar (birinci quldur birinci keçən olur).
Çıxış verilənləri
Girişdəki hər bir test halı üçün, çıxış bir sətirdə bir tam ədəd ehtiva etməlidir: ilk quldurun taxta lövhədən keçməyə başlaması ilə sonuncu quldurun son əşya ilə taxta lövhədən keçməsi arasındakı vaxt saniyə ilə.