Enerji maqnatı
Kiçik Vasya "Enerji maqnatı" adlı yeni bir addım-addım strategiya oyununu oynayır.
Oyunun qaydaları belədir:
Taxta n slotdan ibarətdir və bir sıra şəklində düzülüb.
Hər biri ardıcıl bir və ya iki slot tutan və bir enerji vahidi istehsal edən elektrik stansiyaları mövcuddur.
Hər gedişdə yeni bir elektrik stansiyası tikə bilərsiniz və onu taxtada istədiyiniz yerdə yerləşdirə bilərsiniz. Əgər yeni elektrik stansiyası üçün yer yoxdursa, bəzi köhnə elektrik stansiyalarını silə bilərsiniz.
Hər gedişdən sonra kompüter taxtada yerləşdirilmiş elektrik stansiyalarının istehsal etdiyi enerji miqdarını hesablayır və onu oyundakı ümumi xal sayına əlavə edir.
Vasya, oyunun hər addımında hansı növ elektrik stansiyalarını tikə biləcəyini artıq bilir. O, oyunda əldə edə biləcəyi maksimum xal sayını öyrənmək istəyir. Ona kömək edə bilərsinizmi?
Giriş məlumatları
Birinci sətir n (1 ≤ n ≤ 10^5) - taxtadakı slotların sayını göstərir. İkinci sətir s sətirini ehtiva edir. i-ci simvol 1-ə bərabərdir, əgər i-ci raundda bir slotlu elektrik stansiyası tikə bilsəniz, və simvol 2-yə bərabərdir, əgər i-ci raundda iki slotlu elektrik stansiyası tikə bilsəniz. Oyundakı raundların sayı 10^5-dən çox deyil.
Çıxış məlumatları
Bir ədəd - əldə edilə biləcək maksimum xal sayını göstərin.