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

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

1 секунда

64 мегабайти

Дуже легка

У Сема і Юри є $n$ кульок, кожна кулька або чорна, або біла. Також кожна кулька має свою цінність $c_{i}$ c_i та максимальну кількість разів $a_{i}$ a_i, яку її можна перефарбовувати.

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

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

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \leq n \leq 10^5) — кількість кульок.

Другий рядок містить $n$ цілих чисел $c_{1}, c_{2}, \dots, c_{n}$ c_1, c_2, \ldots, c_n ( $1 \leq c_{i} \leq 1 0^{9}$ 1 \leq c_i \leq 10^9) — цінність $i$ -ої кульки.

Третій рядок містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n ( $1 \leq a_{i} \leq 1 0^{9}$ 1 \leq a_i \leq 10^9) — максимальну кількість разів, скільки можна перефарбувати $i$ -ту кульку.

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

Вихідні дані

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

Приклади

Приклад 1