Tarlanın biçilməsi#10594
Fermer Con təsərrüfatını idarə etməyin demək olar ki, bütün aspektlərində olduqca etibarlıdır, bir istisna olmaqla: o, otu vaxtında və mütəşəkkil şəkildə biçməyi heç bacarmır.
Ferma hər biri vahid sahəyə malik kvadrat xanalardan ibarət böyük iki ölçülü şəbəkədir. t = 0 anında Fermer Con bu xanalardan birində olur və orada otu biçir, beləliklə əvvəlcə yalnız bu bir xana biçilmiş otla örtülü olur. Fermer Conun sonrakı marşrutu əmrdən ibarət ardıcıllıqla təsvir olunur. Məsələn, əgər birinci əmr "W 10" formasındadırsa, onda t = 1-dən t = 10-a qədər (yəni növbəti vahid vaxt ərzində) Fermer Con hər addımda bir xana qərbə hərəkət edir və ziyarət etdiyi hər xanada otu biçir. Bu addımı yerinə yetirdikdən sonra, t = 10 anında o, başlanğıc mövqeyindən xana qərbdə olacaq və keçdiyi bütün xanalarda otu biçmiş olacaq.
Fermer Con o qədər yavaş hərəkət edir ki, onun biçdiyi otun bir hissəsi o biçməyi bitirənə qədər yenidən böyüyə bilər. anında biçilmiş istənilən ot t + x anında yenidən böyüyür.
Fermer Conun marşrutu onun eyni xananı bir neçə dəfə ziyarət etməsinə səbəb ola bilər. Ancaq o, heç vaxt otu hələ biçilmiş olan xananı ziyarət etmədiyini müşahidə edir. Başqa sözlə, hər dəfə o, hər hansı bir xananı ziyarət etdikdə, həmin xananın əvvəlki ziyarəti ən azı vahid vaxt əvvəl baş vermiş olmalıdır ki, ot yenidən böyümüş olsun.
Fermer Conun bu müşahidəsinin doğru qalması üçün mümkün olan maksimal dəyərini müəyyən edin.
Birinci sətirdə n~(1 \le n \le 100) tam ədədi verilir. Növbəti sətirin hər birində "d s" formasında bir əmr verilir, burada — istiqaməti göstərən simvoldur ( = şimal, = şərq, = cənub, = qərb), s~(1 \le s \le 10) isə həmin istiqamətdə atılmalı olan addımların sayıdır.
Fermer Conun heç vaxt biçilmiş otu olan xanaya addım atmadığı maksimal dəyərini çıxarın. Əgər Fermer Con heç bir xananı birdən çox ziyarət etmirsə, çıxarın.
Bu misalda Fermer Con anında bir xananı ziyarət edir, halbuki o, bu xananı əvvəllər anında ziyarət etmişdi. Deməli, ən çox ola bilər; əks halda birinci ziyarətdən sonra ot hələ böyüməmiş olardı. O, həmçinin anında əvvəllər anında ziyarət etdiyi bir xananı ziyarət edir, buna görə də ən çox olmalıdır. Bu iki məhdudiyyətdən birincisi daha sərt olduğundan, -in ən çox ola biləcəyini əldə edirik.
Nümunə 1