У Сема i Юри є n кульок, кожна кулька або чорна, або бiла. Також кожна кулька має свою цiннiсть c[i]
та максимальну кiлькiсть разiв, скiльки її можна перефарбовувати, a
.Тепер же Сем 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ле число n (1 ⩽ n ⩽ 10^5
) — кiлькiсть кульок.
Другий рядок мiстить n цiлих чисел c[1]
; c[2]
; : : : ; c[n]
(1 ⩽ c[i]
⩽ 10^9
) — цiннiсть i-ої кульки.
Третiй рядок мiстить n цiлих чисел a[1]
; a[2]
; : : : ; a[n]
(1 ⩽ a[i]
⩽ 10^9
) — максимальна кiлькiсть разiв, скiльки можна перефарбувати i-ту кiльку.Четвертий рядок мiстить n символiв «W» та «B». i-ий символ рiвний «W», якщо i-та кулька спочатку бiлого кольору, i «B», якщо чорного.
Виведiть два цiлi числа — результати Сема i Юри вiдповiдно