You have to construct a bridge in the city of berland. The bridge consist of n sections (1 to N) There are M constructions teams , the i'th team will work on the section from (li to ri)of the bridge.The bridge is said to be constructed if all the section from (1 to N) are worked on by at least one of teams The cost of building a section is the number of teams that worked on it so the cost of building the bridge is the sum of cost of building all the sections.

and you have to choose a subset of the teams such that bridge is completely constructed and cost is minimum possible,else print -1

Eg:= n=4 m=3 teams={(1,2),(2,3),(3,4)}

optimal way is to choose team and team 3 so output is 4.

Eg:= n=4 m=2 teams={(1,3),(2,4)}

you have to choose all the teams and cost will be 6 as section 2 and 3 will worked on by 2 teams.

Constraints: 1<=n,m<=10^5 1<=li,ri<=n

Asked in contest which is over now

Guys please share your approach