← 返回题目列表

Codeforces · 1091/F

F. 新年与绿头鸭探险

中文机器翻译题面 查看原题

鲍勃是一只鸭子。他要去爱丽丝的巢穴,让那两个人躲起来!

鸭子是终极动物! (图片由西邦提供)

旅程可以表示为一条直线,由 $$$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$$$ 秒。