Wooden sticks - MarisaOJ: Marisa Online Judge
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.
Topic
Basic
Rating
800
Solution (2)
Solution