New Year and the Mallard Expedition

题意翻译

题目大意: 有一被分成 $n$ 段的土地,每段有一个长度 $l_i$ 和一个为 `G`,`W`,`L` 三者中间的属性,定义人物有三种操作:走,游,飞。其中若想通过 `G` 可以走或者飞,`W`可以游或者飞,`L`只能飞。走的速度是 $5s$ 一个单位长度,游是 $3s$ 一个单位长度,飞是 $1s$ 一个单位长度。初始人物能量值为 $0$,每次走/游一个单位长度会使得能量值 $+1$,飞一个单位长度会使得能量值 $-1$。中途不能出现能量值为负数的情况。 求最短通过这些土地的时间。 数据范围:$1 \leq N \leq 10^5,1 \leq l_i \leq 10^{12}$。

题目描述

Bob is a duck. He wants to get to Alice's nest, so that those two can duck! ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1091F/6ea17347fb888fdf90ed3aa4a06fea6a2b533b11.png)Duck is the ultimate animal! (Image courtesy of See Bang)The journey can be represented as a straight line, consisting of $ n $ segments. Bob is located to the left of the first segment, while Alice's nest is on the right of the last segment. Each segment has a length in meters, and also terrain type: grass, water or lava. Bob has three movement types: swimming, walking and flying. He can switch between them or change his direction at any point in time (even when he is located at a non-integer coordinate), and doing so doesn't require any extra time. Bob can swim only on the water, walk only on the grass and fly over any terrain. Flying one meter takes $ 1 $ second, swimming one meter takes $ 3 $ seconds, and finally walking one meter takes $ 5 $ seconds. Bob has a finite amount of energy, called stamina. Swimming and walking is relaxing for him, so he gains $ 1 $ stamina for every meter he walks or swims. On the other hand, flying is quite tiring, and he spends $ 1 $ stamina for every meter flown. Staying in place does not influence his stamina at all. Of course, his stamina can never become negative. Initially, his stamina is zero. What is the shortest possible time in which he can reach Alice's nest?

输入输出格式

输入格式


The first line contains a single integer $ n $ ( $ 1 \leq n \leq 10^5 $ ) — the number of segments of terrain. The second line contains $ n $ integers $ l_1, l_2, \dots, l_n $ ( $ 1 \leq l_i \leq 10^{12} $ ). The $ l_i $ represents the length of the $ i $ -th terrain segment in meters. The third line contains a string $ s $ consisting of $ n $ characters "G", "W", "L", representing Grass, Water and Lava, respectively. It is guaranteed that the first segment is not Lava.

输出格式


Output a single integer $ t $ — the minimum time Bob needs to reach Alice.

输入输出样例

输入样例 #1

1
10
G

输出样例 #1

30

输入样例 #2

2
10 10
WL

输出样例 #2

40

输入样例 #3

2
1 2
WL

输出样例 #3

8

输入样例 #4

3
10 10 10
GLW

输出样例 #4

80

说明

In the first sample, Bob first walks $ 5 $ meters in $ 25 $ seconds. Then he flies the remaining $ 5 $ meters in $ 5 $ seconds. In the second sample, Bob first swims $ 10 $ meters in $ 30 $ seconds. Then he flies over the patch of lava for $ 10 $ seconds. In the third sample, the water pond is much smaller. Bob first swims over the water pond, taking him $ 3 $ seconds. However, he cannot fly over the lava just yet, as he only has one stamina while he needs two. So he swims back for half a meter, and then half a meter forward, taking him $ 3 $ seconds in total. Now he has $ 2 $ stamina, so he can spend $ 2 $ seconds flying over the lava. In the fourth sample, he walks for $ 50 $ seconds, flies for $ 10 $ seconds, swims for $ 15 $ seconds, and finally flies for $ 5 $ seconds.