• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

مهدی که یک لوله کش برتر است، تعدادی چاه آب دارد که به خروجی هایی که با“X” نشان داده می شوند، وصل می شوند. او می خواهد خروجی ها را با استفاده از اتصالاتی که در اختیار دارد به یک شاه لوله وصل کند. برای این کار مهدی قادر به استفاده از دو نوع اتصال است:

• اتصال نوع “A ” که دو خروجی را می گیرد و به اندازه جمع آب خروجی شان، خروجی می دهد.

• اتصال نوع “B ” که دو خروجی را می گیرد و به اندازه بیشینه آب خروجی شان، خروجی می دهد.

مثلا اگر “Y ”و “Z ” دو خروجی باشند، دو سیستم لوله ای “AYZ ” و “BYZ ” را می توان با استفاده از آن ها ساخت. به شما یک سیستم لوله ای داده می شود که متشکل از کاراکترهای "A", "B" و "X" است. به تعداد "X"ها در این سیستم چاه آب با ظرفیت های متفاوت داریم که ظرفیت ها به شما داده می شوند. شما باید با وصل کردن چاه ها به خروجی ها (“X”ها)، بیشترین خروجی آب ممکن سیستم لوله ای داده شده را به دست بیاورید. دقت کنید که هر چاه باید به دقیقا یک خروجی متصل شود.

ورودی

در خط اول به شما عدد $n$ داده می‌شود که برابر با تعداد چاه‌های آب است.
در خط دوم، یک رشته از کاراکترهای "A", "B" و "X" می‌آید.
تضمین می‌شود که این رشته متناظر با یک سیستم لوله‌ای معتبر است و تعداد کاراکترهای "X" برابر $n$ است.
در خط سوم $n$ عدد صحیح $A_i$ $(1 \leq i \leq n)$ به شما داده می‌شود که ظرفیت چاه‌ها است.

خروجی

در یک خط بیشترین مقدار خروجی آب ممکن سیستم را چاپ کنید.

محدودیت‌ها

• $1 \leq n \leq 2 \times 10^5$
• $0 \leq A_i \leq 10^9$

مثال‌ها

ورودی نمونه ۱

3
BXBXX
8 2 3

خروجی نمونه ۱

8

ورودی نمونه ۲

5
AAXXAXAXX
1 1 10 2 8

خروجی نمونه ۲

22

ورودی نمونه ۳

3
AXBXX
8 2 3

خروجی نمونه ۳

11