Mahdieh 是一名开发人员，正在为 Divar 的开放平台（Kenar Divar）开发一个聊天机器人。她希望在机器人中使用 ChatGPT 的 API。这意味着聊天机器人会从 ChatGPT 接收消息并将其转发给用户。当聊天机器人请求 ChatGPT 生成消息时，ChatGPT 会将消息分块（chunks）发送给聊天机器人。因此，对于每个文本块，都有一个 Mahdieh 的聊天机器人接收到它的时间，以及它所包含的字符串。

为了提供流畅的用户体验，Mahdieh 希望她的聊天机器人能够模拟连续打字的效果，即每毫秒输出 $1$ 个字符。显然，在接收到某个字符之前是无法将其打出来的，因此 Mahdieh 必须确保当前要打出的字符在打字前已经被聊天机器人接收到。为了达到她所期望的完美流畅体验，聊天机器人会先等待一段时间而不打任何字，然后开始不间断地打字。现在，Mahdieh 拥有了一条假设消息的所有文本块信息，她需要你的帮助来计算聊天机器人最早可以从什么时间开始打字。

然而，ChatGPT（以及 Mahdieh 的聊天机器人）对文本块应用了 Darkdown 格式，其中包括加粗、斜体、行内代码，甚至还有 emoji 表情！

因此，从 ChatGPT 接收到的消息中包含一些在最终文本中不会被渲染的格式化字符。你只需要确定用于流畅打字的（可见的）已渲染内容。例如，Darkdown 文本 [Let's] (Code!) :rocket: 包含 $24$ 个字符，但其渲染后的文本仅有 $13$ 个字符长：“Let's Code! 🚀”。

你的任务是确定 Mahdieh 最早可以从什么时间开始打字，以保证渲染后的输出能够流畅地呈现。

输入格式

输入的第一行包含一个整数 $k$，表示文本块的数量（$1 \le k \le 10^5$）。

接下来的 $k$ 行包含完整的输入消息，其中每行代表一个非空的文本块。你可以认为 ChatGPT 的消息中不包含换行符，且文本块的开头或结尾可能包含空格。保证所有文本块的总字符数不超过 $10^5$，且最终渲染后的消息不为空。

最后一行包含 $k$ 个由空格分隔的整数 $t_1, t_2, \dots, t_k$，其中 $t_i$ 是聊天机器人从 ChatGPT 接收到第 $i$ 个文本块的时间（$1 \le t_1 < t_2 < \dots < t_k \le 10^9$）。

ChatGPT 的消息具有以下 Darkdown 格式：

• 行内代码块（Inline Code Blocks）：
  • 行内代码包含在一对反引号字符中，例如 `code` 。反引号字符本身不会在最终输出中渲染。你可以认为行内代码内部不包含反引号字符。
  • 行内代码块内部的格式化标记（如 ( 或 \）会被渲染为字面字符，而不会被解析为格式化标记。
• 特殊字符（Special Characters）：
  • 为了渲染特殊字符（(、)、[、]、:、\、` ），只需在它们前面加上一个反斜杠字符进行转义即可（例如 \(、\)、\[、\]、\:、\\、```）。
  • 双反斜杠（\\）在可见输出中会被渲染为单个字面反斜杠。
  • 保证输入中的每个反斜杠后面都紧跟一个特殊字符，行内代码中以及转义反斜杠（\\）之后的情况除外。
• 加粗和斜体格式（Bold and Italic Formatting）：
  • 加粗格式可以通过用圆括号包围文本来实现：(bold)。
  • 斜体格式可以通过用方括号包围文本来实现：[italic]。
  • 不允许嵌套加粗或斜体文本块。此外，一个文本块不能同时既是加粗又是斜体。例如，不允许出现 [(bold and italic) italic] 或 ((superbold) bold)。
  • 加粗或斜体文本内部允许包含行内代码或 emoji。
• Emoji 表情（Emojis）：
  • Emoji 由包围在一对冒号中的非空小写英文字母字符串表示（例如 :smile:、:rocket:）。
• 标点符号和空格（Punctuation and Spaces）：
  • 所有标准标点符号（.、,、!、?、’、-、/）和空格字符都会正常渲染。

保证输入严格遵守上述 Darkdown 格式规则，且最终渲染后的文本是唯一的。

为了计算答案，你只需要考虑可见的（已渲染的）字符，其中包括：

• 普通文本：所有字母、数字、空格、转义的特殊字符，以及不属于任何格式化标记的标准标点符号。
• Emoji 表情：表示为单个概念上的字符。例如，:smile: 被渲染为 😊。请注意，当聊天机器人接收到 emoji 的结束冒号（:）时，该 emoji 对应的单个概念字符即准备好可以被打印。
• 行内代码：反引号字符内部的内容。

输出格式

输出 Mahdieh 的聊天机器人最早可以开始打字的时间，使得机器人能够流畅地打印出整个文本。

样例

输入样例 1

11
The (International Collegiate Programming
Contest) \(` ICPC `\) is
a global [competi
tive programming contest
]
focusing on algorithm
ic problem-solving and teamwork. [Le
t's] test `some ` (more) Darkdown (elemen
ts) here. Visit the Of
ficial ICPC Website\: \(https\://i
cpc.global\) for more info! :rocket:
10 20 30 40 50 60 70 80 90 100 110

输出样例 1

10

输入样例 2

2
l ML5g( RsXFVBdO R)(` gwkz MV
`)
10 1000

输出样例 2

10

说明

为了更好地理解，以下是样例输入最终渲染出的可见消息：

样例 1： The International Collegiate Programming Contest (ICPC) is a global competitive programming contest focusing on algorithmic problem-solving and teamwork. Let’s test some more Darkdown elements here. Visit the Official ICPC Website: (https://icpc.global) for more info! 🚀

样例 2： l ML5g RsXFVBdO Rgwkz MV