{"problem":{"name":"D. Astrodirections","description":{"content":"It is a very rare event that all $N$ colonized planets in the galaxy, numbered $1, 2, \\\\dots, N$, align in order on a straight line. To celebrate the occasion, a grand Astrofestival is held on one of ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10236D"},"statements":[{"statement_type":"Markdown","content":"It is a very rare event that all $N$ colonized planets in the galaxy, numbered $1, 2, \\\\dots, N$, align in order on a straight line. To celebrate the occasion, a grand Astrofestival is held on one of the planets, where unhealthy amounts of Astrohol will be consumed.\n\nAstrodavid doesn't know what Astrohol is, but he's very excited about the Astrogeometry meetup that will take place at the Astrofestival. Unfortunately, he doesn't know on which planet it's held. He may Astrojump between planets on his Astroship, but he has to buy fuel first. Luckily, he reached the fuel station on his home planet just before it closes for the Astrofestival. How much fuel must Astrodavid buy to guarantee that he'll make it to the Astrofestival?\n\nAstrodavid lives on planet $1$. His Astroship has jump power $J$. To take off from planet $p$, he chooses an Astrojump displacement $i$ such $1 <= | i | <= J$, $1 <= p + i <= N$, and his fuel supply is at least $f_i$ units. He will then land on planet $p + i$, his fuel supply having decreased by $f_i$ units. Upon asking for directions there, he'll know if the Astrofestival is held at that planet, a different planet with a higher number, or one with a lower number. As long as he has enough fuel, he may choose to Astrojump again.\n\nThe first line contains two space-separated integers $N$ ($2 <= N <= 4 thin 000$) and $J$ ($1 <= J <= frac(N, 2)$), the number of colonized planets and the jump power, respectively.\n\nThe second line contains $J$ integers, the $i$'th of which is $f_i$, the fuel cost of jumping upward by $i$ planets.\n\nThe third line contains $J$ integers, the $i$'th of which is $f_{-i}$, the fuel cost of jumping downward by $i$ planets.\n\nFor all $i$, $0 <= f_i <= 10 thin 000$.\n\nOutput the minimum number of units of fuel that Astrodavid must buy to guarantee that he'll reach the festival, no matter where it's actually held.\n\n## Input\n\nThe first line contains two space-separated integers $N$ ($2 <= N <= 4 thin 000$) and $J$ ($1 <= J <= frac(N, 2)$), the number of colonized planets and the jump power, respectively.The second line contains $J$ integers, the $i$'th of which is $f_i$, the fuel cost of jumping upward by $i$ planets.The third line contains $J$ integers, the $i$'th of which is $f_{-i}$, the fuel cost of jumping downward by $i$ planets.For all $i$, $0 <= f_i <= 10 thin 000$.\n\n## Output\n\nOutput the minimum number of units of fuel that Astrodavid must buy to guarantee that he'll reach the festival, no matter where it's actually held.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N, Q \\in \\mathbb{Z}^+ $ denote the number of warehouses and routes, respectively.  \nLet $ G = (V, E) $ be a tree with $ |V| = N $, where each edge $ e = (u, v, d) \\in E $ has weight $ d \\in \\mathbb{Z}^+ $, representing the distance between warehouses $ u $ and $ v $.  \nFor each query $ q \\in \\{1, \\dots, Q\\} $, let $ (S_q, F_q, T_q) $ denote the start warehouse, final warehouse, and battery capacity (maximum travel distance on a full charge), respectively.\n\n**Constraints**  \n1. $ 1 \\le N, Q \\le 100{,}000 $  \n2. For each edge $ (u, v, d) \\in E $: $ 1 \\le d \\le 20{,}000 $  \n3. For each query $ q $: $ 1 \\le T_q \\le 20{,}000 $, $ S_q \\ne F_q $  \n\n**Objective**  \nFor each query $ q $, let $ P_q $ be the unique simple path from $ S_q $ to $ F_q $ in $ G $, consisting of edges $ e_1, e_2, \\dots, e_m $ with lengths $ d_1, d_2, \\dots, d_m $.  \nDefine a *stop* as occurring at any warehouse along $ P_q $ (including $ S_q $ and $ F_q $) or at any point along an edge where recharging occurs.  \nSam must ensure that no segment between two consecutive stops exceeds distance $ T_q $.  \nMinimize the total number of stops along $ P_q $, including the start and end warehouses.  \n\nCompute for each $ q $:  \n$$\n\\min \\left\\{ k \\in \\mathbb{Z}^+ \\,\\middle|\\, \\exists \\, s_0 = S_q, s_1, \\dots, s_{k-1} = F_q \\text{ along } P_q \\text{ such that } \\forall i, \\text{dist}(s_i, s_{i+1}) \\le T_q \\right\\}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10236D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}