{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"In 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$."},{"iden":"output","content":"Print 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$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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.","simple_statement":"Jaber starts at floor f1 of building i1 and needs to reach floor f2 of building i2.\n\nHe can:\n- Move up or down 1 floor in the same building.\n- Move horizontally between adjacent buildings **only** if he’s on ground floor (0) or top floor (height).\n- To move to a neighbor’s top floor, that neighbor’s height must be **strictly less** than current building’s height.\n\nBefore each mission, Jaber can use his power once: pick any **contiguous segment** of buildings (not including i1 or i2), and reduce all their heights by the same amount l, where 1 ≤ l ≤ k and l is less than every height in the segment.\n\nAfter using power, buildings return to original heights.\n\nFind the **minimum time** (number of moves) to reach the target for each mission.","has_page_source":false}