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
Vicky:
20160106 20:38:00
yeah think like a kid :p 

infernodragon:
20151122 08:34:28
the problem statement says that a_i and b_i lie between 0 and 1000 but this is not so in test cases they range more than 1000 , even greater than 5000 Last edit: 20151122 08:36:02 

sarvagya:
20150926 01:45:08
Easy dp. Nice question :D 

anshal dwivedi:
20150823 08:23:24
easy logic ..! 

mayank:
20150629 10:32:38
Well, even though it was an easy problem, took me a lot of time to think of the DP approach! :D and silly debugging couts, costed me 3WAs! :P 

Ooo....:
20150531 18:52:57
my century on spoj :) 

Pareek:
20150329 13:38:19
first (successful dp in first attempt) :)


Sahil Dua:
20150110 16:30:18
a_i < b_i doesn't seem to be followed by the test cases! 

Jugal kishor sahu:
20141225 19:55:46
don't give up subham 

happy:
20141212 15:11:07
think simple as possible

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 