SPOJ in Armenian

Տրված է n × n չափի ցանց, որի տողերը և սյուները համարակալված են 1-ից n թվերով (1 ≤ n ≤ 20000)։ Ցանցի յուրաքանչյուր տողում տրված է L(i) և R(i) ծայրակետերերով մի հատված (1 ≤ L(i) ≤ R(i) ≤ n)։ Հարկավոր է գտնել (1, 1) կետից (n, n) կետ տանող և տրված բոլոր հատվածներով անցնող կարճագույն երկարությամբ ճանապարհի երկարությունը։ Այսինքն յուրաքանչյուր i-րդ տողի համար փնտրվող ճանապարհը պետք է անցնի  (i, L(i)), (i, L(i) + 1), (i, L(i) + 2), …, (i, R(i)) կետերով։ Նկատենք, որ յուրաքանչյուր տողից հաջորդ տողին անցնելու համար հարկավոր է մի քայլ կատարել։ Ընդ որում, կարելի է քայլել միայն դեպի ձախ, աջ և ներքև (վերևի մակարդակ գնալ չի կարելի)։ Վերջին n-րդ տողում տրված հատվածի վրայով անցնելուց հետո պետք է հասնել (n, n) կետին։

Մուտքը

Առաջին տողում տրված է ցանցի n չափը։ Հաջորդ n տողերում տրված են L(i) և R(i) ամբողջ թվերը։

Ելքը

Հարկավոր է արտածել մի թիվ՝ (1, 1) կետից (n, n) կետ տանող և բոլոր հատվածներով հերթականությամբ անցնող կարճագույն ճանապարհի երկարությունը։

Օրինակ

Մուտքը.
6
2 6
3 4
1 3
1 2
3 6
4 5

Ելքը.
24