시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 186 124 107 69.032%

문제

매년 가을 대전에서 열리는 대학생 프로그래밍 대회의 묘미 중 하나는 풍선 놀이이다. 시상식에서 스코어보드 공개를 기다리다가 심심해지면, 주위에 있는 풍선을 엮어서, 대회장을 가로지르는 긴 풍선 줄을 만드는 것이다! 이 풍선을 아치형으로 단상 위에 올리면, 본인의 잉여로움을 참가자들에게 뽐낼 수 있는 기회가 생긴다.

심심해진 재현이와 한필이는 풍선 놀이를 위해서 기다란 풍선 줄을 가져왔다. 풍선 줄에는 풍선을 매달 수 있는 N개의 슬롯이 있으며, 각 슬롯은 1번부터 N번까지 번호가 붙어있다. 풍선 줄에, 한필이는 Q번에 걸쳐서 규칙적으로 풍선을 꽂았다. 예를 들면, ’1번 슬롯부터 3개씩 띄어서 풍선을 놓자’ 라고 한필이가 생각했다면, 1, 4, 7, 10, ... 번째 슬롯에 풍선을 놓으며, 슬롯의 번호가 N을 초과하면 풍선을 놓는 것을 그만 둔다. 이미 풍선이 놓여진 슬롯은 건너 뛴다.

Q번에 걸친 풍선 설치가 끝난 후, 한필이는 어떤 슬롯들이 비어 있는 것을 확인했다. 이 슬롯을 메꾸는 풍선을 가져오기 위해서, 총 몇개의 슬롯이 비었는지를 계산해주자.

입력

첫번째 줄에 슬롯 수 N과 풍선들을 꽂는 횟수 Q가 주어진다. (1 ≤ N ≤ 10, 000, 1 ≤ Q ≤ 100)

이후 Q개의 줄에 풍선을 꽂는 방법이 주어진다. 방법은 두 정수 L과 I로 주어지며, ”L번 슬롯부터 I개씩 띄어서 풍선을 놓자” 라는 뜻이다. (1 ≤ L, I ≤ N)

출력

비어있는 슬롯의 개수를 출력하라.

예제 입력

30 3
1 3
3 7
1 4

예제 출력

13

힌트

초기 빈 풍선 줄은 다음과 같다.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

한필이가 1번 슬롯부터 3개씩 띄어서 R 풍선을 설치했다.

R . . R . . R . . R . . R . . R . . R . . R . . R . . R . .

3번 슬롯부터 7개씩 띄어서 B 풍선을 설치했다.

R . B R . . R . . R . . R . . R B . R . . R . B R . . R . .

1번 슬롯부터 4개씩 띄어서 D 풍선을 설치했다.

R . B R D . R . D R . . R . . R B . R . D R . B R . . R D .

최종적으로 13개의 슬롯이 빈다.