{"code":"tkpc06knot","name":"Điểm đại diện","description":"Cho $n$ đoạn thẳng trên trục `Ox`, đoạn thứ $i$ (ký hiệu là $T_i$) bắt đầu tại điểm $x_i$ và có độ dài $l_i$. Ở mỗi đoạn ta cần chọn ra một điểm đại diện của đoạn đó. Biết rằng không có hai đoạn nào hoàn toàn chứa nhau (nói cách khác, không tồn tại $i$ và $j$ khác nhau sau cho $x_j\\leq x_i$ và $x_i+l_i\\leq x_j+l_j$), bạn hãy lập trình xác định một cách chọn $n$ điểm đại diện sao cho khoảng cách giữa hai điểm gần nhất là **lớn nhất có thể**.\r\n\r\nVí dụ, hai hình dưới đây thể hiện hai cách chọn điểm đại diện cho $6$ đoạn thẳng (điểm đại diện được tô đậm màu đen ở mỗi đoạn màu đỏ). Ở cách chọn đầu tiên, hai điểm gần nhất cách nhau $20$ đơn vị độ dài. Ở cách chọn thứ nhì, hai điểm gần nhất cách nhau $25$ đơn vị độ dài.\r\n\r\n
\r\n\r\n
\r\n\r\n

Input

\r\n\r\n- Dòng đầu tiên chứa số nguyên dương $n$ ($2\\leq n\\leq 10^5$).\r\n\r\n- Dòng thứ $i$ trong $n$ dòng tiếp theo chứa hai số nguyên $x_i$ và $l_i$ ($0\\leq x_i\\leq 10^9$, $1\\leq l_i\\leq 10^9$).\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 6\r\n 0 67\r\n 127 36\r\n 110 23\r\n 50 51\r\n 100 12\r\n 158 17\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 25\r\n ```\r\n\r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 6\r\n 0 40\r\n 10 55\r\n 45 28\r\n 90 40\r\n 83 30\r\n 120 30\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 30\r\n ```\r\n\r\n!!! question \"Test 3\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 3\r\n 0 20\r\n 40 10\r\n 100 20\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 50\r\n ```","points":300.0,"partial":true,"time_limit":1.0,"memory_limit":524288,"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}}