{"code":"23hsg9hnoi4","name":"Triển lãm","description":"Bảo tàng thành phố có $N$ bức tranh được đánh số thứ tự từ $1$ đến $N$. Bức tranh thứu $i$ có kích thước là $A_{i}$ và được định giá là $B_{i}$ $(1 \\leq i \\leq N)$. \r\n\r\nGiám đốc bảo tàng muốn chọn một số bức tranh trưng bày trong buổi triển lãm để thu được lợi nhuận lớn nhất thỏa mãn các tiêu chí: \r\n - Phải trưng bày ít nhất một bức tranh. \r\n - Chênh lệch về kích thước giữa các bức tranh được trưng bày càng nhỏ càng tốt. \r\n - Tổng giá trị các bức tranh được trưng bày là lớn nhất. \r\n\r\nGọi $A_{min}$ là kích thước nhỏ nhất, $A_{max}$ là kích thước lớn nhất, $S$ là tổng giá trị của các bức tranh được lựa chọn trưng bày. Lợi nhuận của bảo tàng được tính theo công thức $H = S - (A_{max} - A_{min})$. \r\n\r\n**Yêu cầu**: Hãy giúp Giám đốc bảo tàng tìm $H$ lớn nhất?.  \r\n\r\n#### Input\r\n - Dòng đầu tiên chứa số nguyên $N$ là số lượng các bức tranh $(2 \\leq 500000)$. \r\n - Dòng thứ $i$ trong $N$ dòng tiếp theo chứa hai số nguyên $A_{i}$ và $B_{i}$ là kích thước và định giá của bức tranh thứ $i$ $(1 \\leq A_{i} \\leq 10^{15}, 1 \\leq B_{i} \\leq 10^{9}, 1 \\leq i \\leq N)$\r\n\r\n#### Output\r\n - Số nguyên $H$ lớn nhất tìm được. \r\n\r\n#### Example\r\n\r\n!!! question \"Test \"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3\r\n        2 3\r\n        9 2\r\n        4 5\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        6\r\n        ``` \r\n    ???+ success \"Giải thích\"\r\n        - Chọn các bức tranh là $1$ và $3$ thì: $H = (3 + 5) - (4 - 2) = 6$ là lớn nhất. \r\n        \r\n#### Ràng buộc \r\n - Có $25\\%$ số test tương ứng $25\\%$ số điểm có $N \\leq 16$. \r\n - Có $25\\%$ số test tương ứng $25\\%$ số điểm có $N \\leq 300$. \r\n - Có $25\\%$ số test tương ứng $25\\%$ số điểm có $N \\leq 5000$. \r\n - Có $25\\%$ số test tương ứng $25\\%$ số điểm không có ràng buộc gì thêm.","points":100.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}