eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Перефарбуйте кульку

Перефарбуйте кульку

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

У Сема i Юри є n кульок, кожна кулька або чорна, або бiла. Також кожна кулька має свою цiннiсть c[i] та максимальну кiлькiсть разiв a[i], яку її можна перефарбовувати.

Тепер же Сем i Юра вирiшили зiграти у гру. За один хiд гравець може перефарбувати кульку в чорний або бiлий колiр або пропустити хiд. Одну кульку не можна перефарбовувати бiльше, нiж a[i] разiв. Можна перефарбовувати кульку в той же колiр, в який вона зараз пофарбована. Сем ходить першим. Гра закiнчується, коли жодну кульку вже неможливо перефарбувати або обидва гравцi пiдряд пропустили хiд.

Пiсля цього Сем забирає собi всi бiлi кульки, а Юра всi чорнi. Результат кожного з гравцiв - сума цiнностей його кульок. Обидва гравцi хочуть максимiзувати свiй результат. Знайдiть, який буде кiнцевий результат, якщо обидва гравцi грають оптимально.

Вхiдні дані

Перший рядок мiстить одне цiле число n (1n10^5) - кiлькiсть кульок.

Другий рядок мiстить n цiлих чисел c[1], c[2], ..., c[n] (1c[i]10^9) - цiннiсть i-ої кульки.

Третiй рядок мiстить n цiлих чисел a[1], a[2], ..., a[n] (1a[i]10^9) - максимальна кiлькiсть разiв, скiльки можна перефарбувати i-ту кульку.

Четвертий рядок мiстить n символiв W та B. i-ий символ рiвний W, якщо i-та кулька спочатку бiлого кольору, i B, якщо чорного.

Вихiдні дані

Виведiть два цiлi числа - результати Сема i Юри вiдповiдно.

Пример

Входные данные #1
4
47 7 17 1
2 3 5 4
WBBW
Выходные данные #1
65 7
Источник 2019-2020 ACM-ICPC, SEERC, 1/8 фiналу, 13 квiтня 2019 року