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.

contest
	Wooden sticks
	MARISA
	Supermarket
	That yellow girl not in Mesmerizer
	# Announcement
	String division
	Hotspot
	Dictionary
	Matching numbers
	Arrange flowers
	Stolen precious thing
	Path counting
	Rescue Reisen
	Internet provider
	Tree path

Topic

Basic

Rating

800

Solution (2)

Solution