Yanğın Təlimi#3334
Joko, Cakarta Yanğın Departamenti tərəfindən təşkil edilən yanğın təlimində iştirak edir. Bu təlimin məqsədi, məhdud vaxt ərzində binada tələyə düşmüş könüllüləri (huşsuz insanları canlandıran) xilas etməkdir. Binanın bir neçə mərtəbəsi var və könüllülər bu mərtəbələrdə müxtəlif yerlərə səpələniblər. Hər bir könüllüyə müəyyən bir xal təyin edilib. Yanğınsöndürən namizədi, könüllüləri çıxışa daşıyaraq xilas etməli və bununla da xal qazanmalıdır.
Binanın hər mərtəbəsi hüceyrələrdən ibarət bir şəbəkə şəklində təsvir edilir. Hər bir hüceyrə ya maneə, boş yer, pilləkən, ya da giriş/çıxış nöqtəsi ola bilər.
Namizəd binanın birinci mərtəbəsində yerləşən giriş nöqtəsindən başlayır. O, hər hansı bir bitişik maneəsiz hüceyrəyə (şimal, cənub, qərb və ya şərq istiqamətində) hərəkət edə bilər və ya 1 saniyə ərzində pilləkənlə yuxarı və ya aşağı çıxa bilər. Könüllünü daşıyarkən hərəkət sürəti 2 saniyəyə qədər yavaşlayır. Namizəd könüllünü tapdıqda onu xilas etməyə qərar verə bilər və ya verməyə bilər, lakin xilas etməyə qərar verərsə, onu dayanmadan çıxışa geri daşımalıdır. Eyni anda yalnız bir könüllünü daşıya bilər.
Joko, test binasının mərtəbə planına malikdir. Ona hərəkətlərini planlaşdırmağa kömək edin ki, mümkün olan ən yüksək xalı əldə edə bilsin.
Girişin ilk sətri T (T ≤ 100) ədədini göstərir, bu isə işlərin sayını bildirir. Hər bir işdə beş tam ədəd L (1 ≤ L ≤ 10), H (1 ≤ H ≤ 100), W (1 ≤ W ≤ 100), N (1 ≤ N ≤ 100) və S (1 ≤ S ≤ 10000) var, bunlar mərtəbələrin sayını, hər mərtəbənin hündürlüyünü və enini, huşsuz insanların sayını və verilmiş vaxtı müvafiq olaraq göstərir.
Növbəti L bloklar hər mərtəbənin xəritəsini müvafiq olaraq 1-ci mərtəbədən L-ci mərtəbəyə qədər təsvir edir. Hər mərtəbə H sətirdən ibarətdir, hər biri W simvolu ehtiva edir. Hər mərtəbədə görünə biləcək simvollar:
S Başlanğıc nöqtəsi, həmçinin çıxış nöqtəsi kimi xidmət edir. Yalnız bir başlanğıc/çıxış nöqtəsi olacaq və bu, birinci mərtəbədə görünəcək.
X Maneə, ziyarət edilə bilməyən hüceyrə (divar, yanğın və s.).
U Yuxarı mərtəbəyə bağlanan pilləkən. Yuxarı səviyyədə eyni yerdə D simvolu olacaq. Bu simvol binanın ən yüksək səviyyəsində görünməyəcək.
D Aşağı mərtəbəyə bağlanan pilləkən. Aşağı səviyyədə eyni yerdə U simvolu olacaq. Bu simvol binanın ən aşağı səviyyəsində görünməyəcək.
. Boş yer, ziyarət edilə bilən hüceyrə.
Növbəti N sətir hər biri dörd tam ədəd f[i] (1 ≤ f[i] ≤ L), r[i] (1 ≤ r[i] ≤ H), c[i] (1 ≤ c[i] ≤ W), p[i] (1 ≤ p[i] ≤ 1000) ehtiva edir, bunlar hər bir könüllünün yerini (mərtəbə, sıra, sütun) və bu könüllüyə təyin olunmuş xalı müvafiq olaraq göstərir. Hər bir könüllünün boş yerdə yerləşəcəyini və heç bir iki könüllünün eyni yeri tutmayacağını güman edə bilərsiniz.
Hər bir iş üçün, bir sətirdə, verilmiş vaxt ərzində huşsuz insanları xilas etməklə əldə edə biləcəyi ən yüksək xalı göstərən bir tam ədəd çıxarın.
Nümunə 1