SPOJ in Armenian

Դիցուք ունենք N հատ փայտյա ձողիկներ: Հայտնի են բոլոր ձողիկների երկարությունները և զանգվածները: Կտրող գործիքի միջոցով այդ ձողիկները պետք է հաջորդաբար մշակվեն: Ամեն ձողիկի մշակումից առաջ գործիքը նախապատրաստելու համար անհրաժեշտ է որոշ ժամանակ: Նախապատրաստման ժամանակը որոշվում է հետևյալ կերպ.

1. Առաջին ձողիկի մշակման համար նախապատրաստման ժամանակը 1 րոպե է:
2.  l երկարությամբ և m զանգվածով ձողիկի մշակումից հետո անհրաժեշտ չէ նախապատրաստական աշխատանք եթե հաջորդը մշակվում է l՛ երկարությամբ և m_՛ զանգվածով ձողիկը, որտեղ l ≤ l՛ և m ≤ m՛: Հակառակ դեպքում նախապատրաստման ժամանակը 1 րոպե է:

Անհրաժաշտ է գտնել բոլոր ձողիկները մշակելու համար նախապատրաստման ժամանակների մինիմալ գումարը:

Օրինակ, եթե ունենք 5 ձողիկ հետևյալ երկարություններով և զանգվածներով՝ (9,4), (2,5), (1,2), (5,3) և (4,1) ապա նախապատրաստման ժամանակների մինիմալ գումարը կլինի 2, քանի որ մշակումը կարող ենք իրականացնել հետևյալ հերթականությամբ՝ (4,1), (5,3), (9,4), (1,2), (2,5):

Մուտք

Մուտքում տրված է երկու տող: Առաջին տողում տրված է N ձողիկների քանակը (1 ≤ N ≤ 5000): Հաջորդ տողում տրված են 2N հատ ամբողջ թվեր՝ ձողիկների երկարությունները և զանգվածները հաջորդաբար l₁, m₁, l₂, m₂, ... l_N, m_N:

Ելք

Ելքում անհրաժեշտ է արտածել մեկ ամբողջ թիվ՝ նախապատրաստման ժամանակների մինիմալ գումարը:

Օրինակ

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

Ելքը.
2