미르코의 신문 읽는 시간

미르코의 근무 시간은 총 N분이며, 각 분에는 1부터 N까지 번호가 매겨져 있다. 그에게는 K개의 작업이 주어지고, 각 작업은 시작 시각 P와 처리 시간 T로 정의된다. 즉 그 작업은 P분부터 P+T−1분까지 연속된 T분 동안 진행된다.

미르코는 매 순간 정확히 하나의 작업을 처리하고 있거나, 아니면 아무 작업도 하지 않고 신문을 읽는다. 근무를 시작하는 순간 그는 신문을 읽는(여유) 상태이다.

규칙은 다음과 같다.

• 미르코가 여유 상태일 때 어떤 분에 하나 이상의 작업이 시작되면, 그는 반드시 그중 하나를 즉시 처리하기 시작해야 한다. 같은 분에 시작하는 나머지 작업은 동료들이 대신 처리한다.
• 어떤 작업을 처리하는 도중에 다른 작업이 시작되면, 그 작업은 처리할 수 없다. 현재 작업을 끝낸 뒤에도 그 작업은 이미 지나갔으므로 처리하지 못한다.
• 작업을 끝내면 다시 여유 상태가 되어, 자신이 처리할 수 있는 다음 작업이 시작될 때까지 신문을 읽는다.

같은 분에 여러 작업이 동시에 시작될 때 어떤 작업을 처리할지 잘 선택하면 신문을 읽는 시간을 늘릴 수 있다. 미르코가 최적으로 선택했을 때 신문을 읽을 수 있는 최대 시간(분)을 구하라.

첫째 줄에 두 정수 N과 K가 주어진다 (1 ≤ N ≤ 10000, 1 ≤ K ≤ 10000). N은 근무 시간(분)이고, K는 작업의 개수이다.

다음 K개의 줄에 각 작업의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 두 정수 P와 T가 주어지며, 해당 작업이 P분에 시작하여 T분 동안 진행됨을 뜻한다 (1 ≤ P ≤ N, 1 ≤ P+T−1 ≤ N).

미르코가 신문을 읽으며 보낼 수 있는 최대 시간(분)을 한 줄에 출력한다.