{"raw_statement":[{"iden":"statement","content":"Another semester has ended and Arthur finally achieved his dream of attending Data Structures I with all professors in the Mathematics Department. Now, he can finally pass this subject, but, like everyone expected, he didn't do any PAs (programming assignments), and all deadlines have passed.\n\nFortunately, all PAs can still be submitted for grading, but with a penalty given by: _(late submission time) - (expected deadline time)_ for each PA.\n\nArthur, having taken Data Structures I so many times, knows exactly how much time he needs to complete each assignment. Now, he wants to write a program that determines the minimum sum of penalties that can be achieved, given he can do the PAs in any order.\n\nIt's worth noting that Arthur can't do more than one assignment at a time, since that skill is only learned in Data Structures II. Therefore, if Arthur starts working on an assignment, he needs to finish it before starting any other.\n\nThere is only one problem left: Arthur believes this problem to be unsettlingly similar to a PA, and, therefore, refuses to do it.\n\nHelp Arthur complete this task and, finally, take Data Structures II. \n\nThe first line of input contains two integers 1 ≤ n ≤ 105 and 1 ≤ s ≤ 109, the amount of PAs Arthur needs to do and the time when he started to do them, respectively.\n\nn lines follow, the i-th line contains two integers 1 ≤ ti ≤ 109 and 0 ≤ ei ≤ 109, the time Arthur takes to complete the i-th assignment and the expected deadline time for that assignment.\n\nIt is guaranteed s > ei for all i.\n\nPrint the sum of all penalties if Arthur completes the PAs in the optimal order.\n\nIn the first example, if Arthur does the second PA first, he finishes it at time 2, and finishes the first one at time 4, making his total penalty equals to (2-0)+(4-0) = 6.\n\n"},{"iden":"input","content":"The first line of input contains two integers 1 ≤ n ≤ 105 and 1 ≤ s ≤ 109, the amount of PAs Arthur needs to do and the time when he started to do them, respectively.n lines follow, the i-th line contains two integers 1 ≤ ti ≤ 109 and 0 ≤ ei ≤ 109, the time Arthur takes to complete the i-th assignment and the expected deadline time for that assignment.It is guaranteed s > ei for all i."},{"iden":"output","content":"Print the sum of all penalties if Arthur completes the PAs in the optimal order."},{"iden":"note","content":"In the first example, if Arthur does the second PA first, he finishes it at time 2, and finishes the first one at time 4, making his total penalty equals to (2-0)+(4-0) = 6."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of programming assignments.  \nLet $ s \\in \\mathbb{Z}^+ $ be the start time.  \nFor each assignment $ i \\in \\{1, \\dots, n\\} $:  \n- Let $ t_i \\in \\mathbb{Z}^+ $ be the time required to complete assignment $ i $.  \n- Let $ e_i \\in \\mathbb{Z}_{\\geq 0} $ be the deadline for assignment $ i $.  \n\nIt is given that $ s > e_i $ for all $ i $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq s \\leq 10^9 $  \n3. $ 1 \\leq t_i \\leq 10^9 $ for all $ i $  \n4. $ 0 \\leq e_i \\leq 10^9 $ for all $ i $  \n5. $ s > e_i $ for all $ i $\n\n**Objective**  \nDetermine the permutation $ \\sigma \\in S_n $ that minimizes the total penalty:  \n$$\n\\sum_{i=1}^n \\left( \\left(s + \\sum_{j=1}^i t_{\\sigma(j)} \\right) - e_{\\sigma(i)} \\right)\n$$  \nEquivalently, minimize:  \n$$\n\\sum_{i=1}^n \\left( s + \\sum_{j=1}^i t_{\\sigma(j)} - e_{\\sigma(i)} \\right)\n= n \\cdot s + \\sum_{i=1}^n (n - i + 1) \\cdot t_{\\sigma(i)} - \\sum_{i=1}^n e_{\\sigma(i)}\n$$  \nSince $ \\sum_{i=1}^n e_{\\sigma(i)} = \\sum_{i=1}^n e_i $ is constant, minimize:  \n$$\nn \\cdot s + \\sum_{i=1}^n (n - i + 1) \\cdot t_{\\sigma(i)}\n$$  \nThis is equivalent to minimizing $ \\sum_{i=1}^n (n - i + 1) \\cdot t_{\\sigma(i)} $, which is achieved by sorting assignments in **decreasing order of $ t_i $** (i.e., longest task first).  \n\n**Optimal Order:**  \nSort assignments by $ t_i $ in descending order.  \n\n**Final Objective:**  \nCompute:  \n$$\n\\sum_{i=1}^n \\left( s + \\sum_{j=1}^i t_{\\sigma(j)} - e_{\\sigma(i)} \\right)\n$$  \nwhere $ \\sigma $ is the permutation sorting $ t_i $ in descending order.","simple_statement":"Arthur has n programming assignments to complete. Each assignment i takes time t_i and had deadline e_i. He starts at time s, and s is already past all deadlines. He can only do one assignment at a time, and must finish one before starting the next. The penalty for assignment i is (finish_time - e_i). Find the minimum total penalty by choosing the best order to do the assignments.","has_page_source":false}