Description

Mahdieh 是一名开发人员，正在为 Divar 的开放平台 (Kenar Divar) 开发一个聊天机器人。她想在自己的聊天机器人中使用 ChatGPT 的 API。这意味着聊天机器人从 ChatGPT 接收消息，并将其转发给用户。当聊天机器人要求 ChatGPT 生成一条消息时，ChatGPT 会将消息分块发送给聊天机器人。因此，对于每个数据块，都有聊天机器人接收它的时间以及它包含的字符串。

为了提供流畅的用户体验，Mahdieh 希望她的聊天机器人模拟连续打字的效果，每毫秒输出 1 个字符。显然，任何字符都不能在收到之前被输出，因此 Mahdieh 必须确保聊天机器人在输出当前字符之前已经收到了该字符。为了实现她期望的完美流畅用户体验，聊天机器人会等待一段时间而不输出任何内容，然后开始不间断地输出。现在，Mahdieh 拥有一条假设消息的所有数据块信息，她需要你的帮助来告诉她聊天机器人可以开始输出的最早时间。

然而，ChatGPT（因此也包括 Mahdieh 的聊天机器人）对文本块应用了 Darkdown 格式化，包括粗体、斜体、行内代码，甚至表情符号！😊

因此，从 ChatGPT 接收的消息中包含的格式化字符不会在最终文本中渲染。你只需要为流畅输出确定（可见的）渲染后的内容。例如，Darkdown 文本 "[Let's] (Code!) :rocket:" 由 $24$ 个字符组成，但其渲染后的文本只有 $13$ 个字符长："Let's Code! 🚀"。

你的任务是确定 Mahdieh 为了流畅体验可以开始输出渲染后内容的最早时间。

Input Format

输入的第一行包含一个整数 $k$，表示数据块的数量 ($1 \leq k \leq 10^5$)。接下来的 $k$ 行包含完整的输入消息，其中每一行代表一个非空的数据块。你可以假设 ChatGPT 消息不包含换行符，且数据块可能以空格开头或结尾。保证所有数据块的总字符数不超过 $10^5$，且最终渲染后的消息不为空。最后一行包含 $k$ 个用空格分隔的整数 $t_1, t_2, \ldots, t_k$，其中 $t_i$ 是聊天机器人从 ChatGPT 接收到第 $i$ 个数据块的时间 ($1 \leq t_1 < t_2 < \cdots < t_k \leq 10^9$)。

ChatGPT 消息采用以下 Darkdown 格式化规则：

• 行内代码块：

  • 行内代码由一对反引号字符包裹，例如 code。反引号字符本身不会在最终输出中渲染。你可以假设行内代码内部没有反引号字符。
  • 行内代码块内的格式化标记（如 ( 或 \）会被渲染为字面字符，不会被解析为格式化。

• 特殊字符：

  • 为了渲染特殊字符 ((, ), [, ], :, \, `)，只需在其前面加上反斜杠字符进行转义（例如 \(, \), \[, \], \:, \\, \）。

• 双反斜杠 (\\\\) 在可见输出中被渲染为单个字面反斜杠。

• 保证输入中的每个反斜杠（除了行内代码内以及转义反斜杠之后的情况）后面都跟着一个特殊字符。

• 粗体和斜体格式化：

  • 粗体格式化可通过将文本用括号包裹来实现：(粗体)。
  • 斜体格式化可通过将文本用方括号包裹来实现：[斜体]。
  • 不允许粗体或斜体文本块嵌套。同时，一个文本块不能同时是粗体和斜体。例如，不允许出现 [(粗体且斜体) 斜体] 或 ((超级粗体) 粗体)。
  • 允许在粗体或斜体文本中包含行内代码或表情符号。

• 表情符号：

  • 表情符号由一对冒号包裹的小写英文字母非空字符串表示（例如：::smile:, ::rocket:）。

• 标点符号和空格：

  • 所有标准标点符号 (., ,, !, ?, ', -, /) 和空格字符都会被正常渲染。

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

为了找到答案，你只需要考虑可见（渲染后）的字符，这些字符包括：

• 纯文本：所有字母、数字、空格、转义后的特殊字符以及不属于任何格式化的标准标点符号。
• 表情符号：被视为一个概念性字符。例如，::smile:: 被渲染为 😊。请注意，表情符号的概念性字符在聊天机器人收到其结束冒号 (:) 时才准备好输出。
• 行内代码：反引号字符内的内容。

Output Format

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

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

10

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

10

Hint

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

样例 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：

1 ML5g RsXFVBdO Rgwkz MV

翻译由 DeepSeek V3 完成