Wooden sticks - MarisaOJ: Marisa Online Judge

Wooden sticks

Time limit: 1000 ms
Memory limit: 256 MB
Given $n$ sticks. The $i^{th}$ stick has a length of $a_i$, and there is a marked point on the stick located $b_i$ from one end (and $a_i - b_i$ from the other end). You need to arrange the $n$ sticks parallel to each other such that there exists a straight line passing through all the marked points on the sticks, and this line is perpendicular to the sticks. Determine the maximum length that all the sticks can collectively cover. **You can rotate the stick freely.** For example, with two sticks $(5,2)$ and $(4,1)$, the maximum horizontal length they can cover is $6$.
### Input - The first line contains an integer $n$. - The next $n$ lines each contain two integers $a_i$ and $b_i$. ### Output - Print a single integer, the maximum length that can be covered. ### Constraints - $1 \le n \le 10^5$. - $1 \le a_i, b_i \le 10^9$. ### Example Input: ``` 2 5 2 4 3 ``` Output: ``` 6 ``` Input 2: ``` 4 5 4 5 3 5 2 5 1 ``` Output 2: ``` 8 ``` ### Subtasks - Subtask 1 ($20\\%$ of the points): $1 \le n, a_i, b_i \le 10$. - Subtask 2 ($20\\%$ of the points): $1 \le n \le 2$. - Subtask 3 ($20\\%$ of the points): $1 \le n \le 1000$. - Subtask 4 ($20\\%$ of the points): $b_i = 0$ for all $1 \le i \le n$. - Subtask 5 ($20\\%$ of the points): No additional constraints.