Xxy is the king of the universe. In order to resist the invasion, he ordered the construction of many space warships.Now,he wants to charge his space ships.
He has N space ships.The N ships are numbered from 1 to N and lined up in order.
Xxy has M charging plans.The i-th plan is describe by two positive integers li,ri.It means in this plan, he will charge the ships numbered from li to ri.
Xxy will choose some of these plan.If he totally choose tot plans,x is the number of ships that charged in every plans.Xxy want to maximize the value of min(tot,x).
The first line contains two positive integers N and M(N,M≤300000).
The next M lines,each containing two positive integers li and ri.(li≤ri)
The output contains a positive integer. The maximal value of min(tot,x).