F. Новый год и экспедиция кряквы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Боб — утка. Он хочет попасть в гнездо Алисы, чтобы пойти с ней вместе понырять.

Утка — высшее животное! (Автор изображения — See Bang)

Путешествие Боба может быть представлено в виде прямой линии, состоящей из $$$n$$$ отрезков. Боб находится слева от первого отрезка, а гнездо Алисы — справа от последнего отрезка. Длина каждого отрезка дана в метрах. Каждый отрезок имеет один из трех типов: трава, вода или лава.

Боб может передвигаться тремя способами: плаванием, ходьбой и полетом. Он может переключаться между ними или менять свое направление в любой момент времени (даже если он находится в нецелой координате), и для этого не требуется дополнительное время. Боб может плавать только по воде, ходить только по траве и летать над любой местностью. Чтобы пролететь один метр, нужна $$$1$$$ секунда. Чтобы проплыть один метр, нужно $$$3$$$ секунды. И, чтобы пройти один метр, нужно $$$5$$$ секунд.

У Боба конечное количество энергии. Плавание и ходьба расслабляют его, поэтому его количество энергии увеличивается на $$$1$$$ за каждый метр, который он проходит или проплывает. С другой стороны, летать довольно утомительно, поэтому его количество энергии уменьшается на $$$1$$$ за каждый метр полета. Пребывание на месте никак не влияет на его энергию. Конечно, количество энергии никогда не может становиться отрицательным. В начале количество энергии равно нулю.

За какое минимальное время Боб может достичь гнезда Алисы?

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — количество отрезков.

Вторая строка содержит $$$n$$$ целых чисел $$$l_1, l_2, \dots, l_n$$$ ($$$1 \leq l_i \leq 10^{12}$$$), где $$$l_i$$$ — длина $$$i$$$-го отрезка в метрах.

Третья строка содержит строку $$$s$$$, состоящую из $$$n$$$ символов «G», «W», «L», которые обозначают траву (Grass), воду (Water) и лаву (Lava), соответственно.

Гарантируется, что первый отрезок не лава.

Выходные данные

Выведите одно целое число $$$t$$$ — минимальное количество времени, которое нужно Бобу, чтобы добраться до гнезда Алисы.

Примеры
Входные данные
1
10
G
Выходные данные
30
Входные данные
2
10 10
WL
Выходные данные
40
Входные данные
2
1 2
WL
Выходные данные
8
Входные данные
3
10 10 10
GLW
Выходные данные
80
Примечание

В первом примере Боб сначала проходит $$$5$$$ метров за $$$25$$$ секунд. После этого он пролетает оставшиеся $$$5$$$ метров за $$$5$$$ секунд.

Во втором примере Боб сначала проплывает $$$10$$$ метров за $$$30$$$ секунд. После этого он пролетает над лавой за $$$10$$$ секунд.

В третьем примере водный пруд намного меньше. Боб сначала проплывает по нему за $$$3$$$ секунды. Однако он пока что не может пролететь над лавой, так как у него только одна единица энергии, а ему нужно две. Поэтому он проплывет полметра назад, а потом вернется вперед. Это займет $$$3$$$ секунды. Теперь у него есть $$$2$$$ единицы энергии, значит он сможет пролететь лаву за $$$2$$$ секунды.

В четвертом примере он будет ходить $$$50$$$ секунд, летать $$$10$$$ секунд, плавать $$$15$$$ секунд и в конце летать $$$5$$$ секунд.