MMAXPER - Rectangles Perimeter


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.

Image and video hosting by TinyPic

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
up79: 2017-06-04 07:41:15

a must do problem on DP :)
learnt something new :D

da_201501181: 2017-05-09 12:59:41

Worth to be attempted for beginners..!!

siddharth_0196: 2016-10-08 15:33:45

Bottom-Up works just fine! :D

mario_92: 2016-10-08 15:06:18

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

lalywr: 2016-10-06 00:34:15

AC in 1 Go :D Cakewalk !!
Thanks @Conquistador for suggestion :)
maps + top down + recursion :D

Nallagatla Manikanta: 2016-08-11 06:57:21

accepted in one go :)

surayans tiwari(http://bit.ly/1EPzcpv): 2016-06-24 12:22:03

nice dp

hash7: 2016-05-31 16:16:42

fallen in love with dp and recursion :)

dwij28: 2016-04-25 22:03:06

Simple DP problem, finally it seems like DP is becoming my friend .. :)

Last edit: 2016-04-25 22:03:37
sumitsinghnit: 2016-04-09 16:16:03

Accepted in 1 go.
O(1) space O(n) time.


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