MMAXPER  Rectangles Perimeter
English  Vietnamese 
Given are n rectangles, numbered from 1 to n. We place them tightly on the axis OX, from left to right, according to rectangles' numbers. Each rectangle stays on the axis OX either by its shorter or by its longer side (see the picture below). Compute the length of the upper envelop line, i.e. perimeter's length of the obtained figure minus the length of the left, right and bottom straight line segments of the picture. Write program to find the maximum possible length of the upper envelop line.
Input
On the first line of the standard input, the value of n is written. On each of the next n lines, two integers are given – a_i and b_i – the side lengths of the i_th rectangle.
Constraints: 0 < n < 1000; 0 < a_i < b_i < 1000, for each i = 1, 2, …, n.
Output
On a line of the standard output, your program should write the result as a positive integer.
SAMPLE INPUT: 5 2 5 3 8 1 10 7 14 2 5
SAMPLE OUTPUT: 68
Explanation
A configuration, that yields the maximum length of the upper envelopline, is presented on the picture. The upper envelop line consists of segments DC, CG, GF, FJ, JI, IM, ML, LP, and PO. The total length is 5 + 6 + 3 + 7 + 10 + 13 + 7 + 12 + 5 = 68
Problem for kid  Please, think like kid.hide comments
ankit1cool:
20180621 12:58:04
I solved it using topdown but i don't understand what is the meaning of "Problem for kid  Please, think like kid." does it mean that it has a non dp solution


akash13s:
20180523 18:43:30
Nice problem:) 

vivek_rathi:
20180401 10:14:02
"Problem for kid  Please, think like kid." Mind these words 

sahil070197:
20180310 10:35:47
@mohit_aggarwal I support you! pagal bna rha hai @infernodragon 

mohit_aggarwal:
20180228 12:44:41
@infernodragon


up79:
20170604 07:41:15
a must do problem on DP :)


da_201501181:
20170509 12:59:41
Worth to be attempted for beginners..!! 

siddharth_0196:
20161008 15:33:45
BottomUp works just fine! :D 

mario_92:
20161008 15:06:18
Tried to do without DP but the logic gave WA on running judge(19) ! :/ :P 

lalywr:
20161006 00:34:15
AC in 1 Go :D Cakewalk !!

Added by:  ~!(*(@*!@^& 
Date:  20090217 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  BOI For Kid 08 