鲍勃是一只鸭子。他要去爱丽丝的巢穴,让那两个人躲起来!
鸭子是终极动物! (图片由西邦提供)
旅程可以表示为一条直线,由 $$$n$$$ 段组成。鲍勃位于第一段的左侧,而爱丽丝的巢位于最后一段的右侧。每个部分的长度以米为单位,还有地形类型:草、水或熔岩。
Bob 有三种运动类型:游泳、行走和飞行。他可以在任何时间点在它们之间切换或改变方向(即使他位于非整数坐标),并且这样做不需要任何额外的时间。鲍勃只能在水上游泳,只能在草地上行走,并且可以飞越任何地形。飞行一米需要 $$$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”组成,分别代表草、水和熔岩。
保证第一段不是Lava。
输出
输出一个整数 $$$t$$$ — Bob 联系 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
注意
在第一个示例中,Bob 首先在 $$$25$$$ 秒内行走 $$$5$$$ 米。然后他在 $$$5$$$ 秒内飞行了剩余的 $$$5$$$ 米。
在第二个示例中,Bob 首先在 $$$30$$$ 秒内游了 $$$10$$$ 米。然后他飞过那片熔岩,持续了 $$$10$$$ 秒。
在第三个样本中,水池要小得多。鲍勃首先游过水池,花了 $$$3$$$ 秒。然而,他现在还不能飞越熔岩,因为他只有一种体力,而他需要两种体力。所以他向后游了半米,然后向前游了半米,总共花了 $$$3$$$ 秒。现在他有 $$$2$$$ 耐力,所以他可以在熔岩上飞行 $$$2$$$ 秒。
在第四个样本中,他行走 $$$50$$$ 秒,飞行 $$$10$$$ 秒,游泳 $$$15$$$ 秒,最后飞行 $$$5$$$ 秒。