Dungeon Quest II#3306
Mağara, "Qaranlıq Kütləsi" adlanan, şərin bir narahatlıq nöqtəsi olmuşdu, lakin şeytan kralı və onun bütün əsgərləri qəhrəman tərəfindən məhv edildi və indi orada sülh var.
Bir gün qəhrəman, şeytan kralının yenidən doğulmasından narahat oldu və mağaranın içərisində patrul etməsi üçün təhlükəsizlik agentliyinə müraciət etməyə qərar verdi.
Mağara haqqında məlumatlar aşağıdakı kimidir:
Mağara, hüceyrələrin düzbucaqlı şəbəkəsindən ibarət olan iki ölçülü bir sahə kimi təsvir olunur.
Mağara R×C hüceyrələrə malikdir, burada R sətirlərin sayı və C sütunların sayıdır.
Mağaradakı bəzi hüceyrələrdə tələ var və tələ hüceyrəsinə girənlər zərbə nöqtələrini itirəcəklər.
Tələlərin növü geniş şəkildə dəyişir: bəziləri zərbə nöqtələrini ciddi şəkildə azaldır, digərləri isə daha az zərər verir.
Təhlükəsizlik agentinin patrul etməsi aşağıdakı kimidir:
Agent patruluna mağaranın yuxarı sol küncündən başlayacaq.
Mağaranın yuxarı sol küncündə tələ yoxdur.
Agent, qəhrəmanın müəyyən etdiyi addımları izləyərək patrul edəcək.
Addımlar, agentin patrul zamanı mağaradan kənara çıxmaması üçün təmin ediləcək.
Agent patrul zamanı zərbə nöqtələrini bərpa etmək üçün iksirlər gətirəcək.
Agent daxil olacağı hüceyrəyə girmədən əvvəl iksirlərdən istifadə edə bilər.
İksir növləri də geniş şəkildə dəyişir: bəziləri zərbə nöqtələrini çox bərpa edir, digərləri isə daha az təsirlidir.
Qeyd edək ki, agentin zərbə nöqtəsi HP_max qədər bərpa edilə bilər ki, bu da onun maksimum zərbə nöqtəsini ifadə edir və giriş məlumatları ilə müəyyən edilir.
Agent bir anda bir neçə növ iksirdən istifadə edə bilər.
Əgər agentin zərbə nöqtəsi 0 və ya daha az olarsa, o, öləcək.
Sizin vəzifəniz, agentin patrulunu ölmədən bitirə biləcəyini yoxlayan bir proqram yazmaqdır.
Giriş bir sıra datasetlərdən ibarətdir. Hər bir dataset aşağıdakı formatda verilir:
HP_init HP_max R C a_{1,1} a_{1,2} ... a_{1,C} a_{2,1} a_{2,2} ... a_{2,C} ... a_{R,1} a_{R,2} ... a_{R,C} T [A-Z] d_1 [A-Z] d_2 ... [A-Z] d_T S [UDLR] n_1 [UDLR] n_2 ... [UDLR] n_S P p_1 p_2 ... p_P
Bir datasetin ilk sətri iki tam ədəd HP_init və HP_max (0 < HP_init ≤ HP_max ≤ 1000) ehtiva edir, bu da agentin başlanğıc zərbə nöqtəsini və agentin maksimum zərbə nöqtəsini ifadə edir.
Növbəti sətr R və C (1 ≤ R, C ≤ 100) ehtiva edir. Sonra, mağara haqqında məlumatları təmsil edən C simvoldan ibarət R sətir gəlir. a_{i,j} simvolu i-ci sətirdə və j-ci sütunda a_{i,j} tipli tələ olduğunu bildirir və tələ növü böyük hərflə göstərilir [A-Z].
Növbəti sətir T tam ədədini ehtiva edir, bu da təsvir ediləcək tələ növlərinin sayını bildirir. Sonrakı T sətir böyük hərf [A-Z] və bir tam ədəd d_i (0 ≤ d_i ≤ 1000) ehtiva edir, bu da tələ növünü və verdiyi zərərin miqdarını bildirir.
Növbəti sətir qəhrəmanın agentin patrul marşrutu olaraq təyin etdiyi ardıcıllıqların sayını bildirən S (0 ≤ S ≤ 1000) tam ədədini ehtiva edir. Sonra, S sətir gəlir, hər biri bir simvol və bir tam ədəd n_i (n_i ≤ 1000) ehtiva edir, bu da agentin irəlilədiyi istiqaməti və o istiqamətdə atdığı addımların sayını bildirir. İstiqamət simvolu 'U', 'D', 'L', 'R' olacaq, müvafiq olaraq Yuxarı, Aşağı, Sol, Sağ istiqamətini göstərir və addım istiqamətini bildirir.
Nəhayət, agentin malik olduğu iksir növlərinin sayını bildirən bir tam ədəd P (0 ≤ P ≤ 12) ehtiva edən sətir gəlir. Sonrakı P sətir hər biri bir tam ədəd p_i (0 < p_i ≤ 1000) ehtiva edir ki, bu da bərpa etdiyi zərbə nöqtələrinin miqdarını göstərir.
Giriş iki sıfırdan ibarət bir sətirlə bitir. Bu sətir işlənməməlidir.
Hər bir dataset üçün, agent patrulunu uğurla bitirərsə, bir sətirdə "YES" çap edin, əks halda "NO". Əgər agentin zərbə nöqtəsi patrulun sonunda 0 və ya daha az olarsa, çıxış "NO" olmalıdır.
Nümunə 1