Ali has N friends standing in a line from 1 to N. He decides to take M photos for them. Each photo shows a contiguous range of friends where 3000 oto i shows friends from li to ri inclusive.

After taking the photos, Ali realizes that in each one of the M photos he has exactly one friend wearing a golden hat.

Ali was aware that some of his friends might have golden hats but he had never counted them and does not know which friends have those hats

Based on the photos ranges and the fact that each photo has exactly one friend with a golden hat, determine the maximum number of Ali friends that have golden hats or report -1 if it is impossible to find su an assignment.