Şaxtaçılar#1859

Şaxtaçılar

1 saniyə
256 meqabayt
Asan

İki kömür mədənində, fəhlələrin məhsuldarlığı onların qəbul etdikləri qidanın müxtəlifliyindən birbaşa asılıdır.

Qida mədənə üç növdə qutularda çatdırılır: ət, balıq və çörək (bəli, əgər on il əvvəl "Settlers II" oynamısınızsa, nostalji hiss edə bilərsiniz). Mədənə növbəti qida qutusu çatanda, fəhlələr bu və əvvəlki iki qutunun (yaxud daha az, əgər hələ o qədər qutu gəlməyibsə) tərkibindən asılı olaraq aşağıdakı qaydada müəyyən miqdarda kömür çıxarırlar:

Qutuların mədən şəhərinə hansı ardıcıllıqla çatdırılacağını əvvəlcədən bilirsiniz. Sizin vəzifəniz bu ardıcıllığı iki mədən arasında elə bölməkdir ki, çıxarılan kömürün ümumi miqdarı maksimum olsun.

Qutuları "saxlamaq" və ya bölmək olmaz: hər bir qutu dərhal ya birinci, ya da ikinci mədənə göndərilməlidir. Hər bir mədənə göndərilən qutuların sayı istənilən qədər ola bilər, hətta hamısını bir mədənə göndərmək daha sərfəlidirsə, belə etmək mümkündür. (Yeri gəlmişkən, gələcəkdə dövlət qulluqçusu olsanız, belə etməyin!)

Giriş

Birinci sətirdə — qida qutularının sayı (1 \leq n \leq 100000) verilir. İkinci sətirdə uzunluğu olan simvol sətri verilir və burada hər bir simvol , və ya olmaqla müvafiq olaraq ət, balıq və çörək qutusunu ifadə edir, qutular çatdırılma ardıcıllığı ilə verilib.

Çıxış

Bir ədəd çıxış verin — bu şərtlər daxilində fəhlələrin çıxara biləcəyi maksimum kömür miqdarı.

Nümunələr

Nümunə 1

Loading
Loading