Strawberry
Time limit2sMemory limit512 MB
Strawberries at positions ripen at given times; starting and ending at 0, move at speed 1 and find the minimum time to harvest all after they ripen.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Greedy, Sorting, Math
- Solved
- No attempts yet
Problem
Just Oishi Ichigo Farm (hereafter JOI Farm) is a strawberry farm famous for being long and narrow from east to west, and its entrance is at the westernmost part of the farm. Below, the point k meters east of the entrance is called point k.
There are N strawberries growing in JOI Farm. They are numbered 1 through N. Every strawberry is green until time 0. Strawberry i (1 ≦ i ≦ N) bears fruit at point Ai, and at time Ti it ripens and turns red.
A strawberry cannot be harvested while it is green. That is, strawberry i cannot be harvested until time Ti. You start at time 0 from the farm entrance at point 0 and harvest strawberries while moving east and west at a maximum speed of 1 meter per second. The time it takes to harvest a strawberry can be ignored.
Given information about the strawberry farm, write a program to find the minimum time until you have harvested all strawberries in the red state and returned to the entrance.
Input
The input is given from standard input in the following format.
N
A1 T1
A2 T2
:
AN TN
Output
Print the minimum time until you have harvested all strawberries in the red state and returned to the entrance, on 1 line.
Constraints
1 ≦ N ≦ 100 000.0 ≦ Ai ≦ 1 000 000 000 (= 109)(1 ≦ i ≦ N).0 ≦ Ti ≦ 1 000 000 000 (= 109)(1 ≦ i ≦ N).- All input values are integers.