{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"The 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$."},{"iden":"output","content":"For each query event, print a single line containing an integer, denoting the answer."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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.","simple_statement":"Huriyyah fights n monsters. Each monster has HP (health) and ATK (attack power).  \n\nEach second:  \n1. Huriyyah takes damage = sum of ATK of all alive monsters.  \n2. He attacks one monster. The i-th hit on a monster does i damage (1st hit = 1, 2nd = 2, etc.).  \n\nFind the minimum total damage Huriyyah takes to kill all monsters.","has_page_source":false}