Yuxu
Məktəbli Pətik proqramlaşdırmanı çox sevir və bir gün kompüter qarşısında yuxuya getdi. Yuxuda o, alternativ reallığa düşdüyünü gördü. Bu reallıq R×C ölçülü cədvəl şəklində təsvir edilən düzbucaqlı labirintdən ibarətdir. Məktəbə gecikməmək üçün Pətik labirintdən çıxışı tapmalıdır. Onun başlanğıc mövqeyi 'S' simvolu ilə, alternativ reallıqdan çıxış isə 'E' simvolu ilə göstərilir. Pətik bir hərəkətdə dörd qonşu hüceyrədən birinə (sola, sağa, aşağı, yuxarı) keçə bilər. Əgər hüceyrə divarla (simvol 'X') tutulubsa, ora keçə bilməz. Bəzi hüceyrələrdə dörd rəngdən birinin ('R', 'G', 'B', 'Y') kilidləri olan qapılar var. Bu hüceyrəyə keçmək üçün uyğun rəngdə açar lazımdır. Açarlar çoxistifadəlidir, yəni bir açarla istənilən sayda uyğun kilidi açmaq mümkündür.
Alternativ reallığın hökmdarı Pətikə çıxışa çatmaq üçün açarları almağı təklif edir. Lakin Pətikin çox az pulu var, ona görə də mümkün qədər az pul xərcləyərək çıxışa çatmaq istəyir. Ona açarlar üçün xərclənəcək minimum məbləği müəyyən etməyə kömək edin.
Giriş verilənləri
Birinci sətir testlərin sayını göstərir. Hər bir test iki tam ədəd r və c (1 ≤ r, c ≤ 50) ilə başlayır. Testin ikinci sətiri 'R', 'G', 'B' və 'Y' açarlarının alınma qiymətlərini göstərən 4 tam ədəd p_i (p_i ≤ 100) ehtiva edir. Sonra labirinti təsvir edən r sətir gəlir, hər birində c simvol var. Hər bir labirintdə yalnız bir 'S' və bir 'E' simvolu var.
Çıxış verilənləri
Hər bir test üçün ayrıca sətirdə çıxışa çatmağa imkan verən açar dəstini almaq üçün lazım olan minimum məbləği göstərin. Əgər alternativ reallıqdan çıxış yolu yoxdursa və Pətik dərsləri yatıb qalmağa məhkumdursa, "Sleep" yazın.