"Enterprise"nin Xilas Edilməsi

Starship Enterprise Klingonlarla əhatə olunub! Ən sürətli təxliyə yolunu tapın və onun üçün lazım olan vaxtı hesablayın.

Giriş olaraq, hər bir hüceyrəsində ya Enterprise, ya da müəyyən bir tipdə Klingon hərbi gəmisi olan düzbucaqlı bir şəbəkə verilir. Hər bir Klingon gəmi tipi ilə Enterprise-ın onu məğlub etməsi üçün lazım olan vaxt əlaqələndirilir. Enterprise-ın xilas olması üçün, şəbəkənin sərhədinə gedən müəyyən bir yolda hər bir Klingon gəmisini məğlub etməlidir. Hüceyrələr qonşu sayılır, əgər onların ümumi kənarı varsa, amma küncü yox (yəni dörd qonşu).

Giriş məlumatları

Birinci sətir testlərin sayı t (2 ≤ t ≤ 100) ilə başlayır. Hər bir test, üç ədəd k, w və h olan bir sətirlə başlayır. k (1 ≤ k ≤ 25) - müxtəlif Klingon hərbi gəmilərinin sayı. w (2 ≤ w ≤ 1000) - şəbəkənin eni. h (1 ≤ h ≤ 1000) - şəbəkənin hündürlüyü.

Növbəti k sətirin hər biri böyük latın hərfi - Klingon gəmi tipi və Enterprise-ın onu məğlub etməsi üçün lazım olan vaxtı ehtiva edir. Gəmi tipi "E" ola bilməz. Vaxt dəqiqələrlə verilir və 0 ilə 100000 arasında daxil olmaqla dəyişir. Bütün sətirlər müxtəlif tipləri ehtiva edir.

Növbəti h sətirin hər biri w böyük hərf ehtiva edir (aralarında boşluq olmadan). Bütün h sətirlər arasında yalnız bir "E" hərfi mövcuddur, Enterprise-ın yerini göstərir; qalan bütün böyük hərflər yuxarıda sadalanan k Klingon hərbi gəmi tipindən birini göstərir.

Çıxış məlumatları

Bir tam ədəd çıxarın - gəminin xilas olması üçün kifayət qədər vaxt.