Under construction

Still being built. Things may change

GPT DarkDown

Time limit1sMemory limit2048 MB

Summary
Given Darkdown chunks with arrival times, find the earliest start so the rendered text prints at 1 character per millisecond without waiting.
Level

Medium4 of 10

Topics
String, Simulation, Implementation
Solved
No attempts yet

Problem

Mahdieh is building a chatbot for the Divar open platform (Kenar Divar). She wants the chatbot to use the ChatGPT API. The chatbot receives messages from ChatGPT and forwards them to the user. When the chatbot asks ChatGPT to generate a message, ChatGPT sends the message in chunks. Each chunk comes with the time the chatbot receives it and the string it contains.

For a smooth user experience, the chatbot types 1 character per millisecond. A character cannot be typed before it is received, so each character must already be available when its turn comes. The chatbot waits for a while without typing, then types non-stop from that point on. Mahdieh has the information for every chunk of a hypothetical message, and she wants the earliest time the chatbot can start typing.

ChatGPT text uses Darkdown formatting, which includes bold text, italic text, inline code, and emojis. For example, [Let's] (Code!) :rocket: is 24 characters long, but it renders as Let's Code! 🚀, which is 13 characters. Formatting characters do not appear in the final output, so only the rendered content counts.

The task is to find the earliest time the chatbot can start typing the rendered message so that it prints the whole text smoothly.

Input

The first line contains the number of chunks k (1 ≤ k ≤ 10^5). Each of the next k lines contains one non-empty chunk. Chunks contain no newline characters, and they may start or end with spaces. The total number of characters across all chunks is at most 10^5, and the rendered message is not empty.

The last line contains k space-separated integers t_1, t_2, ..., t_k, where t_i is the time the chatbot receives the i-th chunk (1 ≤ t_1 < t_2 < ... < t_k ≤ 10^9).

The input follows these Darkdown rules.

  • Inline code: text inside a pair of backticks. The backticks are not rendered. Inline code contains no backtick characters. Formatting markers inside inline code, such as ( or \, are rendered as literal characters and are not parsed.
  • Special characters: (, ), [, ], :, , and ' are rendered by putting a backslash before them, as in (, ), [], ], :, \, and '. A double backslash \ renders as one literal backslash. Outside inline code and escaped backslashes, every backslash is followed by a special character.
  • Bold: text wrapped in parentheses, as in (bold).
  • Italic: text wrapped in square brackets, as in [italic].
  • Bold and italic blocks cannot be nested, and a block cannot be both bold and italic. Forms such as [(bold and italic) italic] and ((superbold) bold) do not occur.
  • Inline code and emojis can appear inside bold or italic text.
  • Emojis: a non-empty string of lowercase English letters between two colons, such as :smile: or :rocket:.
  • Periods, commas, exclamation marks, question marks, apostrophes, hyphens, slashes, and spaces render normally.

The input always follows these rules, and the rendered text is unique.

Output

Print the earliest time at which the chatbot can start typing the rendered message so that the whole text is typed without pauses.

Examples2

  1. Example 1

    Input
    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
    Expected output
    10

  2. Example 2

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