{"problem":{"name":"H. Skyscraper","description":{"content":"At the main street of Byteland, there will be built $n$ skyscrapers, standing sequentially one next to other. If look leftside right, sequence of their height will be $a_1, a_2, \\\\dots, a_n$. Initial","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10222H"},"statements":[{"statement_type":"Markdown","content":"At the main street of Byteland, there will be built $n$ skyscrapers, standing sequentially one next to other. If look leftside right, sequence of their height will be $a_1, a_2, \\\\dots, a_n$.\n\nInitially the street is empty, every skyscraper's height is $0$. Hamster is the leader of the construction team. In each stage, Hamster can select a range $[ l, r ]$, then the team will work on this range. Specifically, assume the height sequence is $h_1, h_2, \\\\dots, h_n$, then $h_l, h_{l + 1}, \\\\dots, h_r$ will increase by $1$ during this stage. When $h_i = a_i$ holds for all $i in [ 1, n ]$, the project will be closed.\n\nThe plan may be changed for many times. There will be $m$ events of $2$ kinds below:\n\nThe first line of the input contains an integer $T (1 <= T <= 1000)$, denoting the number of test cases.\n\nIn each test case, there are two integers $n, m (1 <= n, m <= 100000)$ in the first line, denoting the number of skyscrapers and events.\n\nIn the second line, there are $n$ integers $a_1, a_2,..., a_n (1 <= a_i <= 100000)$.\n\nFor the next $m$ lines, each line describes an event.\n\nIt is guaranteed that $sum n <= 10^6$ and $sum m <= 10^6$.\n\nFor each query event, print a single line containing an integer, denoting the answer.\n\n## Input\n\nThe first line of the input contains an integer $T (1 <= T <= 1000)$, denoting the number of test cases.In each test case, there are two integers $n, m (1 <= n, m <= 100000)$ in the first line, denoting the number of skyscrapers and events.In the second line, there are $n$ integers $a_1, a_2,..., a_n (1 <= a_i <= 100000)$.For the next $m$ lines, each line describes an event.It is guaranteed that $sum n <= 10^6$ and $sum m <= 10^6$.\n\n## Output\n\nFor each query event, print a single line containing an integer, denoting the answer.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ be the number of monsters.  \n- Let $ M_k = \\{(HP_i, ATK_i) \\mid i \\in \\{1, \\dots, n_k\\}\\} $ be the set of monsters, where $ HP_i $ is the health point and $ ATK_i $ is the attack value of the $ i $-th monster.\n\n**Constraints**  \n1. $ 1 \\le T \\le 10^3 $  \n2. For each test case $ k $:  \n   - $ 1 \\le n_k \\le 10^5 $  \n   - $ 1 \\le HP_i, ATK_i \\le 10^5 $ for all $ i \\in \\{1, \\dots, n_k\\} $  \n3. $ \\sum_{k=1}^T n_k \\le 10^6 $\n\n**Objective**  \nMinimize the total damage suffered by the hero, defined as:  \n$$\n\\sum_{t=1}^T \\left( \\sum_{\\substack{\\text{alive monsters } i \\\\ \\text{at second } t}} ATK_i \\right)\n$$  \nwhere at each second:  \n- The hero takes damage equal to the sum of $ ATK_i $ over all alive monsters.  \n- Then, the hero chooses one monster $ i $ to attack, dealing $ c_i $ damage to it, where $ c_i $ is the number of times monster $ i $ has been attacked so far (starting at 1).  \n- Monster $ i $ dies when cumulative damage to it $ \\ge HP_i $.  \n\nThe goal is to find the **minimum total damage** the hero must take over all seconds until all monsters are dead, by optimally choosing the order of attacks.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10222H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}