{"problem":{"name":"P. Proooooooooooooofer","description":{"content":"You are given an encrypted string, encrypted using a certain algorithm. Decrypt it! Encryption algorithm gives a string t of length n and converts it to a pair (s, a) where s is a string of length n ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CFP"},"statements":[{"statement_type":"Markdown","content":"You are given an encrypted string, encrypted using a certain algorithm. Decrypt it!\n\nEncryption algorithm gives a string t of length n and converts it to a pair (s, a) where s is a string of length n and a is a sequence of integers of length n - 2.\n\nThe first line, contains an integer n. (3 ≤ n ≤ 105).\n\nThe second line, contains string s. The third line contains n - 2 integers a1, a2, ..., an - 2 seperated by space.\n\nEach character of s is a lower case English letter (1 ≤ ai ≤ n and 1 ≤ i ≤ n - 2).\n\nPrint t in the only line of output.\n\n## Input\n\nThe first line, contains an integer n. (3 ≤ n ≤ 105).The second line, contains string s. The third line contains n - 2 integers a1, a2, ..., an - 2 seperated by space.Each character of s is a lower case English letter (1 ≤ ai ≤ n and 1 ≤ i ≤ n - 2).\n\n## Output\n\nPrint t in the only line of output.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"地牢中的零级骑士陷入困境！该地牢可抽象为一条长度为 $D$ 的长路径，骑士初始位于位置 0。地牢中会发生两种事件：\n\n作为骑士，他绝不能后退。他的路上有 $n$ 个怪物和 $m$ 个商店，第 $i$ 个怪物位于位置 $a_i$，生命值为 $h_i$，若他无法击败它，则需要花费 $f_i$ 枚金币通过。第 $i$ 个商店位于位置 $b_i$，出售能将其生命值提升至 $l_i$ 的药水，购买该药水需要 $w_i$ 枚金币。\n\n他通过地牢所需的最少金币数是多少？\n\n第一行包含三个整数 $D, n, m$ $(1 lt.eq D lt.eq 10^9, 1 lt.eq n, m lt.eq 10^5)$。\n\n接下来 $n$ 行，每行包含三个整数 $a_i, h_i, f_i$ $(1 lt.eq a_i lt.eq D, 1 lt.eq h_i, f_i lt.eq 10^9)$。\n\n接下来 $m$ 行，每行包含三个整数 $b_i, l_i, w_i$ $(1 lt.eq b_i lt.eq D, 1 lt.eq l_i, w_i lt.eq 10^9)$。\n\n所有怪物和商店的位置互不相同。\n\n输出骑士通过地牢所需的最少金币数。\n\n在第一个示例中，一种最优解如下：\n\n在第一个怪物处，他支付 $30$ 枚金币通过。\n\n在第一个商店，他花费 $10$ 枚金币购买魔法药水。\n\n他可以用当前生命值 $5$ 击败第二个怪物。\n\n在第三个怪物处，他支付 $100$ 枚金币通过。\n\n在第二个商店，他什么也不买。\n\n在第三个商店，他花费 $50$ 枚金币购买魔法药水，恢复至生命值 $30$。\n\n他可以轻松击败最后一个怪物。\n\n总花费为 $30 + 10 + 100 + 50 = 190$。\n\n## Input\n\n第一行包含三个整数 $D, n, m$ $(1 lt.eq D lt.eq 10^9, 1 lt.eq n, m lt.eq 10^5)$。接下来 $n$ 行，每行包含三个整数 $a_i, h_i, f_i$ $(1 lt.eq a_i lt.eq D, 1 lt.eq h_i, f_i lt.eq 10^9)$。接下来 $m$ 行，每行包含三个整数 $b_i, l_i, w_i$ $(1 lt.eq b_i lt.eq D, 1 lt.eq l_i, w_i lt.eq 10^9)$。所有怪物和商店的位置互不相同。 \n\n## Output\n\n骑士通过地牢所需的最少金币数。\n\n[samples]\n\n## Note\n\n在第一个示例中，一种最优解如下：在第一个怪物处，他支付 $30$ 枚金币通过。在第一个商店，他花费 $10$ 枚金币购买魔法药水。他可以用当前生命值 $5$ 击败第二个怪物。在第三个怪物处，他支付 $100$ 枚金币通过。在第二个商店，他什么也不买。在第三个商店，他花费 $50$ 枚金币购买魔法药水，恢复至生命值 $30$。他可以轻松击败最后一个怪物。总花费为 $30 + 10 + 100 + 50 = 190$。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ D \\in \\mathbb{Z}^+ $ be the length of the dungeon.  \nLet $ M = \\{(a_i, h_i, f_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ be the set of monsters, where $ a_i $ is position, $ h_i $ is health, and $ f_i $ is fee to bypass.  \nLet $ S = \\{(b_i, l_i, w_i) \\mid i \\in \\{1, \\dots, m\\} \\} $ be the set of shops, where $ b_i $ is position, $ l_i $ is health level restored, and $ w_i $ is cost.  \n\nLet $ P = \\text{sorted}(\\{0\\} \\cup \\{a_i \\mid (a_i, h_i, f_i) \\in M\\} \\cup \\{b_i \\mid (b_i, l_i, w_i) \\in S\\} \\cup \\{D\\}) $ be the ordered sequence of key positions.  \n\nLet $ \\text{health}(x) $ denote the knight’s health just before reaching position $ x $, initialized to $ 0 $ at $ x = 0 $.  \nLet $ \\text{cost} $ denote total coins spent, initialized to $ 0 $.  \n\n**Constraints**  \n1. $ 1 \\le D \\le 10^9 $  \n2. $ 1 \\le n, m \\le 10^5 $  \n3. All positions in $ M \\cup S $ are distinct and lie in $ [1, D] $.  \n4. The knight moves only forward, from position $ 0 $ to $ D $.  \n5. At each monster at $ a_i $: if current health $ < h_i $, must pay $ f_i $ coins to bypass; otherwise, pass without cost.  \n6. At each shop at $ b_i $: may optionally pay $ w_i $ coins to set current health to $ l_i $.  \n\n**Objective**  \nMinimize total coins spent to reach position $ D $, subject to:  \n- At each monster position $ a_i $, $ \\text{health}(a_i) \\ge h_i $ or pay $ f_i $.  \n- At each shop position $ b_i $, may upgrade health to $ l_i $ at cost $ w_i $.  \n- Health is non-decreasing and starts at $ 0 $.  \n\nFormally, find:  \n$$\n\\min \\sum_{\\text{bypasses}} f_i + \\sum_{\\text{purchases}} w_j\n$$  \nover all valid sequences of bypasses and potion purchases, such that health constraints at monsters are satisfied.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CFP","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}