{"problem":{"name":"A. Nate and Actual 3D Girls","description":{"content":"Nate is tired of 2D girls and has decided that this year he will try looking for the real thing. Although Nate is too shy to go out and talk to one, he realized he could avoid having to go through the","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10205A"},"statements":[{"statement_type":"Markdown","content":"Nate is tired of 2D girls and has decided that this year he will try looking for the real thing. Although Nate is too shy to go out and talk to one, he realized he could avoid having to go through the ordeal of real-life interaction by writing an anonymous _tegami_ (letter) to his prospective 3D girl. He can do this by cutting up letters from his old Pokémon trading cards.\n\nHowever, as much as Nate would be happy with any living, breathing 3D girl, he still wants someone with substance. To provide the recipient with a challenge, he decided to *encrypt* his letter using a simple cipher. \n\nNate will think of a number $k$ which is the number of times he will shift the alphabet to the left. For example, if Nate chooses $k = 3$, then the alphabet _[a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z]_ is transformed to _[d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, a, b, c]_.\n\nThis transformed alphabet is what he uses to write the _tegami_.\n\nHelp Nate determine if he was able to obtain enough letters from his $n$ trading cards to write the _tegami_ if each letter can only be used once.\n\nThe first line of input contains three space-separated integers $n$, $m$, and $k$, respectively. The first number, $n$, is the number of words Nate cut out. The second number, $m$, is the number of words in the _tegami_. The third number, $k$, is the number of times the alphabet is shifted, respectively.\n\nThe second line of input contains $n$ space-separated strings, the words Nate cut out. \n\nThe third line of input contains $m$ space-separated words consisting only of lowercase English letters, the message that Nate wants to encrypt and send to his potential 3D girl. \n\n*Constraints*\n\n$1 <= n <= 100$\n\n $1 <= m <= 100$\n\n $0 <= k <= 100$\n\n The sum of the lengths of the words Nate cut out will not exceed $10^5$.\n\n The sum of the lengths of the words in the message Nate wants to encrypt will not exceed $10^5$.\n\nOutput _Make her kokoro go doki-doki!_ if Nate has enough letters to write the encrypted _tegami_, and _It is gonna be daijoubu._ if Nate doesn't have enough letters.\n\nIn the second example, the alphabet is shifted $k = 22$ characters to the left as shown below:\n\n*Before:*  _a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z_\n\n*After:*  _w, x, y, z, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v_\n\nUsing this new alphabet, the message is encrypted into _sehh ukq ck pk qjzan pda opwno sepd ia_.\n\nNate can write the word _sehh_ using the letter _s_ from the _kangaskhan_ card, a letter _e_ from the _pelipper_ card, the letter _h_ from the _qwilfish_ card, and the letter _h_ from the _kangaskhan_ card. \n\nNotice that different letters may come from the same card, but each letter may only be used once. He could've also used the _zapdos_ card instead of the _kangaskhan_ card for the letter _s_. If you continue this process you will find that he has enough characters to write the entire _tegami_.\n\n## Input\n\nThe first line of input contains three space-separated integers $n$, $m$, and $k$, respectively. The first number, $n$, is the number of words Nate cut out. The second number, $m$, is the number of words in the _tegami_. The third number, $k$, is the number of times the alphabet is shifted, respectively.The second line of input contains $n$ space-separated strings, the words Nate cut out. The third line of input contains $m$ space-separated words consisting only of lowercase English letters, the message that Nate wants to encrypt and send to his potential 3D girl. *Constraints*$1 <= n <= 100$ $1 <= m <= 100$ $0 <= k <= 100$ The sum of the lengths of the words Nate cut out will not exceed $10^5$. The sum of the lengths of the words in the message Nate wants to encrypt will not exceed $10^5$.\n\n## Output\n\nOutput _Make her kokoro go doki-doki!_ if Nate has enough letters to write the encrypted _tegami_, and _It is gonna be daijoubu._ if Nate doesn't have enough letters.\n\n[samples]\n\n## Note\n\nIn the second example, the alphabet is shifted $k = 22$ characters to the left as shown below:*Before:*  _a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z_*After:*  _w, x, y, z, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v_Using this new alphabet, the message is encrypted into _sehh ukq ck pk qjzan pda opwno sepd ia_.Nate can write the word _sehh_ using the letter _s_ from the _kangaskhan_ card, a letter _e_ from the _pelipper_ card, the letter _h_ from the _qwilfish_ card, and the letter _h_ from the _kangaskhan_ card. Notice that different letters may come from the same card, but each letter may only be used once. He could've also used the _zapdos_ card instead of the _kangaskhan_ card for the letter _s_. If you continue this process you will find that he has enough characters to write the entire _tegami_.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, M, e \\in \\mathbb{Z}^+ $ be given:  \n- $ n $: number of rows.  \n- $ M $: maximum number of column pairs (i.e., up to $ M+1 $ columns).  \n- $ e $: number of distinct edge types between adjacent columns.  \n\nLet $ E = \\{ (u_k, v_k, w_k) \\}_{k=1}^e $ be the set of edge types, where each $ (u_k, v_k, w_k) $ denotes a bidirectional edge between row $ u_k $ in column $ i $ and row $ v_k $ in column $ i+1 $, with cost $ w_k $, for all $ i \\in [1, M] $.  \n\nFor each $ m \\in [1, M] $, define the graph $ G_m $ as follows:  \n- Vertices: $ V_m = \\{ (x, y) \\mid x \\in [1, n], y \\in [1, m+1] \\} $.  \n- Edges: For each $ k \\in [1, e] $ and each $ i \\in [1, m] $, include edge $ ((u_k, i), (v_k, i+1)) $ with weight $ w_k $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq M \\leq 10^5 $  \n3. $ 1 \\leq e \\leq 2 \\times 10^5 $  \n4. $ 1 \\leq u_k, v_k \\leq n $, $ 1 \\leq w_k \\leq 30 $  \n5. All edge types are distinct: $ (u_k, v_k) \\neq (u_{k'}, v_{k'}) $ for $ k \\neq k' $.  \n6. For each $ m \\in [1, M] $, the subgraph induced by columns $ i $ and $ i+1 $ (for any $ i \\in [1, m] $) is connected.  \n\n**Objective**  \nFor each $ m \\in [1, M] $, compute the minimum total cost of a spanning tree of $ G_m $.  \n\nThat is, output $ M $ integers: for each $ m $,  \n$$\n\\text{MinCost}(m) = \\min_{T \\subseteq E_m} \\left\\{ \\sum_{e \\in T} w(e) \\,\\middle|\\, T \\text{ is a spanning tree of } G_m \\right\\}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10205A","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}