{"problem":{"name":"G. Hungry Canadian","description":{"content":"Teodoro just moved to Canada. He is having a hard time there as the cost of living is higher than he expected. He is short on money so he decided to eat a string, as they are cheaper than food. He kno","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10148G"},"statements":[{"statement_type":"Markdown","content":"Teodoro just moved to Canada. He is having a hard time there as the cost of living is higher than he expected. He is short on money so he decided to eat a string, as they are cheaper than food. He knows exactly how hungry he is, so he will buy a string with exactly K letters.\n\nTeodoro went to a string store and saw that the price of a string depends on which letters are adjacent. For example, the price of the string \"bca\" is equal to the cost of putting \"c\" after \"b\" and \"a\" after \"c\". The costs of adjacent letters are given in a 26 × 26 matrix P, in which pi, j corresponds to the cost of putting the j-th letter of the alphabet after the i-th letter of the alphabet, e.g., p3, 7 is the cost of putting \"g\" after \"c\". Notice that the cost of putting i after j may not be the same as putting j after i, that is, pi, j may be different from pj, i.\n\nTeodoro wants to order a string of size K with the minimum possible price. He is so hungry that he can barely think. Please help him find the cheapest string of size K.\n\nThe first line of the input contains an integer K (2 ≤ K ≤ 104), indicating the size of the string Teodoro will order.\n\nThe next 26 lines contain matrix P. The j-th integer of the i-th line corresponds to pi, j (0 ≤ pi, j ≤ 103), indicating the cost of putting the j-th letter of the alphabet right after the i-th letter of the alphabet.\n\nOutput a single integer: the minimum cost to create a string of size K.\n\n## Input\n\nThe first line of the input contains an integer K (2 ≤ K ≤ 104), indicating the size of the string Teodoro will order.The next 26 lines contain matrix P. The j-th integer of the i-th line corresponds to pi, j (0 ≤ pi, j ≤ 103), indicating the cost of putting the j-th letter of the alphabet right after the i-th letter of the alphabet.\n\n## Output\n\nOutput a single integer: the minimum cost to create a string of size K.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ K \\in \\mathbb{Z} $ with $ 2 \\leq K \\leq 10^4 $ be the length of the string.  \nLet $ P \\in \\mathbb{R}^{26 \\times 26} $ be a cost matrix where $ P[i][j] $ denotes the cost of appending the $ j $-th letter (0-indexed, 'a' to 'z') after the $ i $-th letter.\n\n**Constraints**  \n- $ 0 \\leq P[i][j] \\leq 10^3 $ for all $ i, j \\in \\{0, 1, \\dots, 25\\} $.\n\n**Objective**  \nFind the minimum total cost of a string $ s = s_1 s_2 \\dots s_K $, where each $ s_i \\in \\{0, 1, \\dots, 25\\} $, defined as:  \n$$\n\\min_{s_1, \\dots, s_K \\in \\{0,\\dots,25\\}} \\sum_{i=1}^{K-1} P[s_i][s_{i+1}]\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10148G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}