İ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:
Əgər hər üç (yaxud daha az) qutu eyni növdəndirsə, bir vahid kömür çıxarılır;
Əgər bu üç (və ya az) qutuda iki növ qida varsa, iki vahid kömür çıxarılır;
Əgər bu üç qutu üç müxtəlif növ qidadan ibarətdirsə, üç vahid kömür çıxarılır.
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!)
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.
Bir ədəd çıxış verin — bu şərtlər daxilində fəhlələrin çıxara biləcəyi maksimum kömür miqdarı.
Nümunə 1