{"problem":{"name":"B. Efficient market","description":{"content":"According to the efficient-market hypothesis you cannot systematicaly make money from stock market. While the validity of that is debatable, so it happened that you came into possesion of a leak of st","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10241B"},"statements":[{"statement_type":"Markdown","content":"According to the efficient-market hypothesis you cannot systematicaly make money from stock market. While the validity of that is debatable, so it happened that you came into possesion of a leak of stock prices for the next $n$ days. There is $m$ companies and on the day $i$ you know that the stock of the company number $j$ is going to have value of $a_{i , j}$ pounds. We assume that you start with $d$ pounds on day $0$. What is the most money you can have after those $n$ days? Each day you can make as many transactions as you like and we assume that the value of stocks stays constant on each day.\n\nIn the first row there are three numbers: $1 <= n <= 50$, $1 <= m <= 1000$ and $0. 00 <= d <= 10^6$. In the following $m$ rows there are descriptions of stock values of each company for each day $1. 00 <= d_{i , j} <= 10. 00$.\n\nPrint the maximal amount of money you can have by the end of the last day, up to two decimal places (we accept error of $0. 01$). You can assume that the answer will be no bigger than $10^9$.\n\n## Input\n\nIn the first row there are three numbers: $1 <= n <= 50$, $1 <= m <= 1000$ and $0. 00 <= d <= 10^6$. In the following $m$ rows there are descriptions of stock values of each company for each day $1. 00 <= d_{i , j} <= 10. 00$.\n\n## Output\n\nPrint the maximal amount of money you can have by the end of the last day, up to two decimal places (we accept error of $0. 01$). You can assume that the answer will be no bigger than $10^9$.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ be the number of buildings and missions.  \nLet $ H = (h_1, h_2, \\dots, h_n) $ be the sequence of building heights, where $ h_i \\in \\mathbb{Z}^+ $.  \nFor each mission $ j \\in \\{1, \\dots, m\\} $, let:  \n- $ i_{1,j}, i_{2,j} \\in \\{1, \\dots, n\\} $, $ i_{1,j} \\ne i_{2,j} $: start and end building indices.  \n- $ f_{1,j}, f_{2,j} \\in \\mathbb{Z} $: start and end floor levels, $ 0 \\le f_{1,j} \\le h_{i_{1,j}} $, $ 0 \\le f_{2,j} \\le h_{i_{2,j}} $.  \n- $ k_j \\in \\mathbb{Z}^+ $: upper bound on the decrease value $ l $.\n\n**Constraints**  \n1. $ 2 \\le n \\le 2 \\times 10^5 $, $ 1 \\le m \\le 2 \\times 10^5 $  \n2. $ 1 \\le h_i \\le 5 \\times 10^8 $  \n3. $ 1 \\le k_j \\le 5 \\times 10^8 $  \n4. For each mission $ j $, Jaber may apply a segment modification:  \n   - Choose a contiguous segment $ [L, R] \\subseteq \\{2, \\dots, n-1\\} $ (excluding $ i_{1,j}, i_{2,j} $)  \n   - Decrease all $ h_i $ for $ i \\in [L,R] $ by $ l \\in \\mathbb{Z} $, where $ 1 \\le l \\le \\min(k_j, \\min_{i \\in [L,R]} h_i - 1) $  \n   - The segment modification is temporary and resets after each mission.\n\n**Movement Rules**  \nFrom any position $ (b, f) $ (building $ b $, floor $ f $), Jaber can:  \n1. Go down: $ (b, f) \\to (b, f-1) $ if $ f > 0 $  \n2. Go up: $ (b, f) \\to (b, f+1) $ if $ f < h_b $  \n3. Move horizontally on ground floor: $ (b, 0) \\to (b \\pm 1, 0) $ if $ 1 \\le b \\pm 1 \\le n $  \n4. Move horizontally on roof: $ (b, h_b) \\to (b \\pm 1, h_{b \\pm 1}) $ if $ h_{b \\pm 1} < h_b $\n\n**Objective**  \nFor each mission $ j $, compute the minimum number of moves to reach $ (i_{2,j}, f_{2,j}) $ from $ (i_{1,j}, f_{1,j}) $, **after optimally choosing** a segment $ [L,R] $ (not containing $ i_{1,j}, i_{2,j} $) and a decrease value $ l \\in [1, \\min(k_j, \\min_{i \\in [L,R]} h_i - 1)] $ to reduce heights of buildings in $ [L,R] $, thereby enabling cheaper roof transitions.\n\n**Note**: The optimal $ l $ and segment $ [L,R] $ may reduce intermediate building heights to allow new roof-to-roof moves (Rule 4), reducing total travel time.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10241B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}