{"raw_statement":[{"iden":"statement","content":"Some telecommunications company plans to simultaneously introduce two innovative smartphones to the market. These smartphones will be called ,,Innophone\" and ,,Innophone Plus\". The devices are ready for production, but there is one more thing the company management needs to decide about – the optimal price for each type of smartphone.\n\nThe company hired analysts to analyze the market. They conducted a study in which they built the following model. There are $n$ potential buyers of innovative smartphones. The $i$-th buyer uses the following algorithm, characterized by two numbers $a_i$ and $b_i$ ($a_i >= b_i$):\n\nThe company wants to set the prices of ,,Innophone\" and ,,Innophone Plus\" in such a way that both prices are integers, the price of ,,Innophone\" is not greater than the price of ,,Innophone Plus\", and the total value of sold phones is the highest.\n\nWrite a program that finds the maximum possible total value of the sold smartphones, i.e. the total amount of money the buyers will pay.\n\nThe first line of the input contains an integer $n$ ($1 <= n <= 150 thin 000$) — the number of potential buyers.\n\nThe $i$-th of the next $n$ lines contains two integers $a_i$ and $b_i$ ($0 <= b_i <= a_i <= 10^9$) — the parameters used in the algorithm of the $i$-th potential buyer.\n\nPrint a single line — the maximum possible total value of sold smartphones.\n\n$$ \\begin{array}{|c|c|c|c|} \\hline \\text{Subtask} & \\text{Points} & \\text{Constraints} & \\text{Dependencies} \\\\ \\hline 1 & 9 & n \\le 100; b_i \\le a_i \\le 100 & 0 \\\\ \\hline 2 & 10 & n \\le 300 & 0, 1 \\\\ \\hline 3 & 16 & n \\le 3000 & 0, 1, 2 \\\\ \\hline 4 & 11 & n \\le 10^5; b_i = 0 & \\\\ \\hline 5 & 16 & n \\le 10^5; a_i = b_i & \\\\ \\hline 6 & 7 & n \\le 50\\,000 & 0 - 3 \\\\ \\hline 7 & 7 & n \\le 75\\,000 & 0 - 3, 6 \\\\ \\hline 8 & 8 & n \\le 100\\,000 & 0 - 7 \\\\ \\hline 9 & 8 & n \\le 125\\,000 & 0 - 8 \\\\ \\hline 10 & 8 & n \\le 150\\,000 & 0 - 9 \\\\ \\hline \\end{array}$$\n\nYou will get points for a group if you pass all tests in this group and all groups listed in the dependencies. The group $0$ denotes the sample test(s) from the statement.\n\nIn the first sample test, the optimal prices of ,,Innophone\" and ,,Innophone Plus\" are $40$ and $70$ respectively. The first and fifth buyer will buy ,,Innophone Plus\", while the second and third buyer will buy ,,Innophone\". The fourth buyer will not buy anything. The total value of sold smartphones is then $70 + 40 + 40 + 0 + 70 = 220$.\n\nIn the second sample test, you need to set the price of ,,Innophone Plus\" to $50$. The price of ,,Innophone\" doesn't matter.\n\n"},{"iden":"input","content":"The first line of the input contains an integer $n$ ($1 <= n <= 150 thin 000$) — the number of potential buyers.The $i$-th of the next $n$ lines contains two integers $a_i$ and $b_i$ ($0 <= b_i <= a_i <= 10^9$) — the parameters used in the algorithm of the $i$-th potential buyer."},{"iden":"output","content":"Print a single line — the maximum possible total value of sold smartphones."},{"iden":"scoring","content":"$$ \\begin{array}{|c|c|c|c|} \\hline \\text{Subtask} & \\text{Points} & \\text{Constraints} & \\text{Dependencies} \\\\ \\hline 1 & 9 & n \\le 100; b_i \\le a_i \\le 100 & 0 \\\\ \\hline 2 & 10 & n \\le 300 & 0, 1 \\\\ \\hline 3 & 16 & n \\le 3000 & 0, 1, 2 \\\\ \\hline 4 & 11 & n \\le 10^5; b_i = 0 & \\\\ \\hline 5 & 16 & n \\le 10^5; a_i = b_i & \\\\ \\hline 6 & 7 & n \\le 50\\,000 & 0 - 3 \\\\ \\hline 7 & 7 & n \\le 75\\,000 & 0 - 3, 6 \\\\ \\hline 8 & 8 & n \\le 100\\,000 & 0 - 7 \\\\ \\hline 9 & 8 & n \\le 125\\,000 & 0 - 8 \\\\ \\hline 10 & 8 & n \\le 150\\,000 & 0 - 9 \\\\ \\hline \\end{array}$$You will get points for a group if you pass all tests in this group and all groups listed in the dependencies. The group $0$ denotes the sample test(s) from the statement."},{"iden":"examples","content":"Input5\n80 20\n60 50\n40 40\n15 10\n70 30\nOutput220\nInput1\n50 0\nOutput50\n"},{"iden":"note","content":"In the first sample test, the optimal prices of ,,Innophone\" and ,,Innophone Plus\" are $40$ and $70$ respectively. The first and fifth buyer will buy ,,Innophone Plus\", while the second and third buyer will buy ,,Innophone\". The fourth buyer will not buy anything. The total value of sold smartphones is then $70 + 40 + 40 + 0 + 70 = 220$.In the second sample test, you need to set the price of ,,Innophone Plus\" to $50$. The price of ,,Innophone\" doesn't matter."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of buyers.  \nFor each buyer $ i \\in \\{1, \\dots, n\\} $, let $ a_i, b_i \\in \\mathbb{Z}_{\\geq 0} $ with $ b_i \\leq a_i $ be their valuation parameters.  \n\nLet $ p_1, p_2 \\in \\mathbb{Z} $ denote the prices of \"Innophone\" and \"Innophone Plus\", respectively, with $ 0 \\leq p_1 \\leq p_2 $.  \n\nEach buyer $ i $ chooses:  \n- \"Innophone Plus\" if $ p_2 \\leq a_i $ and $ p_2 \\leq b_i + (a_i - b_i) \\cdot \\mathbb{I}_{p_1 > b_i} $,  \n- \"Innophone\" if $ p_1 \\leq b_i $,  \n- nothing otherwise.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 150\\,000 $  \n2. $ 0 \\leq b_i \\leq a_i \\leq 10^9 $ for all $ i $  \n3. $ p_1, p_2 \\in \\mathbb{Z} $, $ 0 \\leq p_1 \\leq p_2 $  \n\n**Objective**  \nMaximize the total revenue:  \n$$\n\\max_{\\substack{p_1, p_2 \\in \\mathbb{Z} \\\\ 0 \\leq p_1 \\leq p_2}} \\sum_{i=1}^n \n\\begin{cases}\np_2 & \\text{if } p_2 \\leq a_i \\text{ and } (p_1 > b_i \\text{ or } p_2 \\leq b_i) \\\\\np_1 & \\text{if } p_1 \\leq b_i \\text{ and } (p_2 > a_i \\text{ or } p_1 > b_i) \\\\\n0 & \\text{otherwise}\n\\end{cases}\n$$\n\n**Simplified Choice Rule (per buyer $ i $):**  \nBuyer $ i $ selects:  \n- \"Innophone Plus\" if $ p_2 \\leq a_i $ and $ p_2 \\leq a_i $ and $ p_1 > b_i $,  \n- \"Innophone\" if $ p_1 \\leq b_i $,  \n- nothing if $ p_1 > b_i $ and $ p_2 > a_i $.  \n\nThus, equivalently:  \n- If $ p_2 \\leq b_i $: buys Plus (since $ p_1 \\leq p_2 \\leq b_i $)  \n- Else if $ p_1 \\leq b_i < p_2 \\leq a_i $: buys Plus  \n- Else if $ p_1 \\leq b_i $ and $ p_2 > a_i $: buys Innophone  \n- Else if $ b_i < p_1 \\leq p_2 \\leq a_i $: buys Plus  \n- Else: buys nothing  \n\nBut the cleanest formulation is:  \nBuyer $ i $ buys:  \n- \"Innophone Plus\" if $ p_2 \\leq a_i $ and $ (p_1 > b_i \\text{ or } p_2 \\leq b_i) $  \n- \"Innophone\" if $ p_1 \\leq b_i $ and $ p_2 > a_i $  \n- Nothing otherwise  \n\nThus, revenue from buyer $ i $:  \n$$\nR_i(p_1, p_2) = \n\\begin{cases}\np_2 & \\text{if } p_2 \\leq a_i \\text{ and } (p_1 > b_i \\text{ or } p_2 \\leq b_i) \\\\\np_1 & \\text{if } p_1 \\leq b_i \\text{ and } p_2 > a_i \\\\\n0 & \\text{otherwise}\n\\end{cases}\n$$\n\n**Objective:**  \n$$\n\\max_{\\substack{p_1, p_2 \\in \\mathbb{Z} \\\\ 0 \\leq p_1 \\leq p_2}} \\sum_{i=1}^n R_i(p_1, p_2)\n$$","simple_statement":"Set two prices for two phones: Innophone (price p1) and Innophone Plus (price p2), with p1 ≤ p2.  \nEach buyer i chooses:  \n- Buy Innophone Plus if p2 ≤ a_i  \n- Else buy Innophone if p1 ≤ b_i  \n- Else buy nothing  \n\nFind p1, p2 (integers, p1 ≤ p2) to maximize total money from all buyers.","has_page_source":false}