{"problem":{"name":"F. Fastest Speedrun","description":{"content":"The classic video game \"Prince of Python\" comprises $n$ levels, numbered from $1$ to $n$. You are going to speedrun this game by finishing all of the levels as fast as possible, and you can beat them ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10248F"},"statements":[{"statement_type":"Markdown","content":"The classic video game \"Prince of Python\" comprises $n$ levels, numbered from $1$ to $n$. You are going to speedrun this game by finishing all of the levels as fast as possible, and you can beat them in any order that you want.\n\nYou enter each level equipped with one of $n + 1$ magical items. In the beginning, you only have item $0$ in your inventory. Once you beat a level, you get to keep the item numbered the same as that level. For example, on finishing level $5$, you obtain a mighty #cf_span(class=[tex-font-style-underline], body=[Gauntlet of 5 Fingers]) you may equip thereafter instead of the less-acclaimed #cf_span(class=[tex-font-style-underline], body=[Sword of 0 Damage]) you always start out with.\n\nBeating a level can take different amounts of time depending on which item you take into the level with you. Higher-numbered items are more powerful, so if playing by the rules it is always at least as fast to finish the level with a higher-numbered item as with a lower-numbered item.\n\nHowever, each level also has a shortcut left in by the developers. The shortcut for a level can be accessed by applying a specific item in an unconventional way. By doing so you can finish the level as fast as, or even faster than if you had used any of the other items.\n\nHow long will it take you to beat all of the levels of the game?\n\nThe input consists of: \n\n The $i$th such line starts with two integers $x_i$ and $s_i$ ($0 <= x_i <= n$, $1 <= s_i <= 10^9$), the shortcut item for level $i$ and the completion time for level $i$ when using the shortcut.\n\n The remainder of the line has $n + 1$ integers $a_{i , 0}, \\\\dots, a_{i , n}$ ($10^9 >= a_{i , 0} >= a_{i , 1} >= \\\\dots >= a_{i , n} >= s_i$), where $a_{i , j}$ is the completion time for level $i$ when playing by the rules using item $j$. \n\nOutput the minimum time it takes to beat, in any order, all of the levels in the game.\n\n## Input\n\nThe input consists of:   One line containing an integer $n$ ($1 <= n <= 2 thin 500$), the number of levels.  $n$ lines, describing the levels. The $i$th such line starts with two integers $x_i$ and $s_i$ ($0 <= x_i <= n$, $1 <= s_i <= 10^9$), the shortcut item for level $i$ and the completion time for level $i$ when using the shortcut. The remainder of the line has $n + 1$ integers $a_{i , 0}, \\\\dots, a_{i , n}$ ($10^9 >= a_{i , 0} >= a_{i , 1} >= \\\\dots >= a_{i , n} >= s_i$), where $a_{i , j}$ is the completion time for level $i$ when playing by the rules using item $j$. \n\n## Output\n\nOutput the minimum time it takes to beat, in any order, all of the levels in the game.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of words, with $ 2 \\leq n \\leq 2500 $.  \nLet $ W = (w_1, w_2, \\dots, w_n) $ be the sequence of words, where each $ w_i $ is a string of letters with $ |w_i| \\leq 80 $.  \n\nLet $ L \\in \\mathbb{Z}^+ $ denote the line width (in characters).  \nFor a given $ L $, the text is typeset greedily: words are placed on a line until adding the next word would exceed $ L $; a single space separates adjacent words on the same line.  \n\nDefine the *gap sequence* $ G_L = (g_1, g_2, \\dots, g_{n-1}) $, where $ g_i $ is the horizontal gap (number of spaces) between word $ w_i $ and $ w_{i+1} $, determined by the line breaks under width $ L $.  \n\nA *river* of length $ r $ is a vertical sequence of $ r $ consecutive spaces, aligned across $ r $ consecutive lines, formed by gaps at the same horizontal position.  \n\n**Constraints**  \n1. $ L $ must be at least $ \\max_i |w_i| $ and at most $ \\sum_{i=1}^n |w_i| + (n-1) $.  \n2. For each $ L $, the typesetting is deterministic via greedy line breaking.  \n\n**Objective**  \nFind the line width $ L^* $ that maximizes the length of the longest river in the typeset text.  \nIf multiple $ L $ yield the same maximum river length, choose the smallest such $ L $.  \nOutput $ L^* $ and the length of the longest river under $ L^* $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10248F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}