시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB121178770865.434%

문제

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

심심해진 재현이와 한필이는 풍선 놀이를 위해서 기다란 풍선 줄을 가져왔다. 풍선 줄에는 풍선을 매달 수 있는 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)

출력

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

예제 입력 1

30 3
1 3
3 7
1 4

예제 출력 1

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개의 슬롯이 빈다.

W3sicHJvYmxlbV9pZCI6IjYyNDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ0OGRcdWMxMjAgXHViMTgwXHVjNzc0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWI5ZTRcdWIxNDQgXHVhYzAwXHVjNzQ0IFx1YjMwMFx1YzgwNFx1YzVkMFx1YzExYyBcdWM1ZjRcdWI5YWNcdWIyOTQgXHViMzAwXHVkNTU5XHVjMGRkIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1Yjc5OFx1YmMwZCBcdWIzMDBcdWQ2OGNcdWM3NTggXHViYjE4XHViYmY4IFx1YzkxMSBcdWQ1NThcdWIwOThcdWIyOTQgXHVkNDhkXHVjMTIwIFx1YjE4MFx1Yzc3NFx1Yzc3NFx1YjJlNC4gXHVjMmRjXHVjMGMxXHVjMmRkXHVjNWQwXHVjMTFjIFx1YzJhNFx1Y2Y1NFx1YzViNFx1YmNmNFx1YjRkYyBcdWFjZjVcdWFjMWNcdWI5N2MgXHVhZTMwXHViMmU0XHViOWFjXHViMmU0XHVhYzAwIFx1YzJlY1x1YzJlY1x1ZDU3NFx1YzljMFx1YmE3NCwgXHVjOGZjXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWQ0OGRcdWMxMjBcdWM3NDQgXHVjNWVlXHVjNWI0XHVjMTFjLCBcdWIzMDBcdWQ2OGNcdWM3YTVcdWM3NDQgXHVhYzAwXHViODVjXHVjOWMwXHViOTc0XHViMjk0IFx1YWUzNCBcdWQ0OGRcdWMxMjAgXHVjOTA0XHVjNzQ0IFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQhIFx1Yzc3NCBcdWQ0OGRcdWMxMjBcdWM3NDQgXHVjNTQ0XHVjZTU4XHVkNjE1XHVjNzNjXHViODVjIFx1YjJlOFx1YzBjMSBcdWM3MDRcdWM1ZDAgXHVjNjJjXHViOWFjXHViYTc0LCBcdWJjZjhcdWM3NzhcdWM3NTggXHVjNzg5XHVjNWVjXHViODVjXHVjNmMwXHVjNzQ0IFx1Y2MzOFx1YWMwMFx1Yzc5MFx1YjRlNFx1YzVkMFx1YWM4YyBcdWJmNTBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFlMzBcdWQ2OGNcdWFjMDAgXHVjMGRkXHVhZTM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyZWNcdWMyZWNcdWQ1NzRcdWM5YzQgXHVjN2FjXHVkNjA0XHVjNzc0XHVjNjQwIFx1ZDU1Y1x1ZDU0NFx1Yzc3NFx1YjI5NCBcdWQ0OGRcdWMxMjAgXHViMTgwXHVjNzc0XHViOTdjIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWFlMzBcdWIyZTRcdWI3ODAgXHVkNDhkXHVjMTIwIFx1YzkwNFx1Yzc0NCBcdWFjMDBcdWM4MzhcdWM2NTRcdWIyZTQuIFx1ZDQ4ZFx1YzEyMCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNDhkXHVjMTIwXHVjNzQ0IFx1YjllNFx1YjJlYyBcdWMyMTggXHVjNzg4XHViMjk0IE5cdWFjMWNcdWM3NTggXHVjMmFjXHViODZmXHVjNzc0IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhYzAxIFx1YzJhY1x1Yjg2Zlx1Yzc0MCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YmQ5OVx1YzViNFx1Yzc4OFx1YjJlNC4gXHVkNDhkXHVjMTIwIFx1YzkwNFx1YzVkMCwgXHVkNTVjXHVkNTQ0XHVjNzc0XHViMjk0IFFcdWJjODhcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIFx1YWRkY1x1Y2U1OVx1YzgwMVx1YzczY1x1Yjg1YyBcdWQ0OGRcdWMxMjBcdWM3NDQgXHVhZjQyXHVjNTU4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHViYTc0LCAmcnNxdW87MVx1YmM4OCBcdWMyYWNcdWI4NmZcdWJkODBcdWQxMzAgM1x1YWMxY1x1YzUyOSBcdWI3NDRcdWM1YjRcdWMxMWMgXHVkNDhkXHVjMTIwXHVjNzQ0IFx1YjE5M1x1Yzc5MCZyc3F1bzsgXHViNzdjXHVhY2UwIFx1ZDU1Y1x1ZDU0NFx1Yzc3NFx1YWMwMCBcdWMwZGRcdWFjMDFcdWQ1ODhcdWIyZTRcdWJhNzQsIDEsIDQsIDcsIDEwLCAuLi4gXHViYzg4XHVjOWY4IFx1YzJhY1x1Yjg2Zlx1YzVkMCBcdWQ0OGRcdWMxMjBcdWM3NDQgXHViMTkzXHVjNzNjXHViYTcwLCBcdWMyYWNcdWI4NmZcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIE5cdWM3NDQgXHVjZDA4XHVhY2ZjXHVkNTU4XHViYTc0IFx1ZDQ4ZFx1YzEyMFx1Yzc0NCBcdWIxOTNcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YWRmOFx1YjljY1x1YjQ1NFx1YjJlNC4gXHVjNzc0XHViYmY4IFx1ZDQ4ZFx1YzEyMFx1Yzc3NCBcdWIxOTNcdWM1ZWNcdWM5YzQgXHVjMmFjXHViODZmXHVjNzQwIFx1YWM3NFx1YjEwOCBcdWI2ZjRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlFcdWJjODhcdWM1ZDAgXHVhYzc4XHVjZTVjIFx1ZDQ4ZFx1YzEyMCBcdWMxMjRcdWNlNThcdWFjMDAgXHViMDVkXHViMDljIFx1ZDZjNCwgXHVkNTVjXHVkNTQ0XHVjNzc0XHViMjk0IFx1YzViNFx1YjVhNCBcdWMyYWNcdWI4NmZcdWI0ZTRcdWM3NzQgXHViZTQ0XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NDQgXHVkNjU1XHVjNzc4XHVkNTg4XHViMmU0LiBcdWM3NzQgXHVjMmFjXHViODZmXHVjNzQ0IFx1YmE1NFx1YWZiOFx1YjI5NCBcdWQ0OGRcdWMxMjBcdWM3NDQgXHVhYzAwXHVjODM4XHVjNjI0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYywgXHVjZDFkIFx1YmE4NyBcdWFjMWNcdWM3NTggXHVjMmFjXHViODZmXHVjNzc0IFx1YmU0NFx1YzVjOFx1YjI5NFx1YzljMFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NzRcdWM4ZmNcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMyYWNcdWI4NmYgXHVjMjE4IE5cdWFjZmMgXHVkNDhkXHVjMTIwXHViNGU0XHVjNzQ0IFx1YWY0Mlx1YjI5NCBcdWQ2OWZcdWMyMTggUVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwLCAwMDAsIDEgJmxlOyBRICZsZTsgMTAwKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgUVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVkNDhkXHVjMTIwXHVjNzQ0IFx1YWY0Mlx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJjMjlcdWJjOTVcdWM3NDAgXHViNDUwIFx1YzgxNVx1YzIxOCBMXHVhY2ZjIElcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCAmcmRxdW87TFx1YmM4OCBcdWMyYWNcdWI4NmZcdWJkODBcdWQxMzAgSVx1YWMxY1x1YzUyOSBcdWI3NDRcdWM1YjRcdWMxMWMgXHVkNDhkXHVjMTIwXHVjNzQ0IFx1YjE5M1x1Yzc5MCZyZHF1bzsgXHViNzdjXHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gKDEgJmxlOyBMLCBJICZsZTsgTik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMmFjXHViODZmXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2QwOFx1YWUzMCBcdWJlNDggXHVkNDhkXHVjMTIwIFx1YzkwNFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4uIC4gLiAuIC4gLiAuIC4gLiAuIC4gLiAuIC4gLiAuIC4gLiAuIC4gLiAuIC4gLiAuIC4gLiAuIC4gLjxcL3ByZT5cclxuXHJcbjxwPlx1ZDU1Y1x1ZDU0NFx1Yzc3NFx1YWMwMCAxXHViYzg4IFx1YzJhY1x1Yjg2Zlx1YmQ4MFx1ZDEzMCAzXHVhYzFjXHVjNTI5IFx1Yjc0NFx1YzViNFx1YzExYyBSIFx1ZDQ4ZFx1YzEyMFx1Yzc0NCBcdWMxMjRcdWNlNThcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcblIgLiAuIFIgLiAuIFIgLiAuIFIgLiAuIFIgLiAuIFIgLiAuIFIgLiAuIFIgLiAuIFIgLiAuIFIgLiAuPFwvcHJlPlxyXG5cclxuPHA+M1x1YmM4OCBcdWMyYWNcdWI4NmZcdWJkODBcdWQxMzAgN1x1YWMxY1x1YzUyOSBcdWI3NDRcdWM1YjRcdWMxMWMgQiBcdWQ0OGRcdWMxMjBcdWM3NDQgXHVjMTI0XHVjZTU4XHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG5SIC4gQiBSIC4gLiBSIC4gLiBSIC4gLiBSIC4gLiBSIEIgLiBSIC4gLiBSIC4gQiBSIC4gLiBSIC4gLjxcL3ByZT5cclxuXHJcbjxwPjFcdWJjODggXHVjMmFjXHViODZmXHViZDgwXHVkMTMwIDRcdWFjMWNcdWM1MjkgXHViNzQ0XHVjNWI0XHVjMTFjIEQgXHVkNDhkXHVjMTIwXHVjNzQ0IFx1YzEyNFx1Y2U1OFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuUiAuIEIgUiBEIC4gUiAuIEQgUiAuIC4gUiAuIC4gUiBCIC4gUiAuIEQgUiAuIEIgUiAuIC4gUiBEIC48XC9wcmU+XHJcblxyXG48cD5cdWNkNWNcdWM4ODVcdWM4MDFcdWM3M2NcdWI4NWMgMTNcdWFjMWNcdWM3NTggXHVjMmFjXHViODZmXHVjNzc0IFx1YmU0OFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjYyNDYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgRmxvd2VyIEdhcmRlbiIsImRlc2NyaXB0aW9uIjoiPHA+SW1hZ2luZSBCZXRzeSYjMzk7cyBzdXJwcmlzZSBhcyBzaGUgcm91bmRlZCB0aGUgYmFybiBhbmQgZGlzY292ZXJlZCB0aGF0IEZhcm1lciBKb2huIGhhZCBidWlsdCBhIHNlY3JldCBncmVlbmhvdXNlIHRoYXQgd2FzIG5vdyBicmltbWluZyB3aXRoIGdvcmdlb3VzIGZsb3dlcnMuIEhlciBtaW5kIHJhbiB3aWxkIGFzIHZpc2lvbnMgb2YgYSBnb3JnZW91cyBjb2xvcmZ1bCBnYXJkZW4gc3dpcmxlZCB0aHJvdWdoIGhlciBsaXR0bGUgYm92aW5lIGJyYWluLjxcL3A+XHJcblxyXG48cD4mcXVvdDtJIHRoaW5rIEkmIzM5O2xsIG1ha2UgYSBsb25nIHJvdyBvZiBGICg3ICZsdDs9IEYgJmx0Oz0gMTAsMDAwKSBmbG93ZXJzIGFnYWluc3QgdGhlIGZhciBmZW5jZSwmcXVvdDsgc2hlIHRob3VnaHQuICZuYnNwOyZxdW90O0kmIzM5O2xsIHBsYW50IHJvc2VzIGluIGV2ZXJ5IDNyZCBzbG90LCBiZWdvbmlhcyBpbiBldmVyeSA3dGggc2xvdCB0aGF0IGlzIHN0aWxsIG9wZW4sIGFuZCBkYWlzaWVzIGluIGV2ZXJ5IDR0aCBzbG90IHRoYXQgaXMgc3RpbGwgb3Blbi4mcXVvdDsgQmV0c3kgd29uZGVyZWQgaG93IG1hbnkgb3BlbiBzbG90cyB3b3VsZCByZW1haW4uIFNoZSByZWFsaXplZCB0aGF0IHRoZSBudW1iZXIgd291bGQgZGVwZW5kIG9uIHdoaWNoIHNsb3Qgc2hlIHN0YXJ0ZWQgcGxhbnRpbmcgd2hlbiBzaGUgaW50ZW5kZWQgdG8gZmlsbCBldmVyeSBOdGggc2xvdCB3aXRoIGEga2luZCBvZiBmbG93ZXIuPFwvcD5cclxuXHJcbjxwPkhlbHAgQmV0c3kga25vdyBob3cgbWFueSBvcGVuIHNsb3RzIHdpbGwgcmVtYWluLiBSZWFkIGEgc2V0IG9mIEsgKDEgJmx0Oz0gSyAmbHQ7PSAxMDApIHBsYW50aW5nIGRlc2NyaXB0b3JzLCBlYWNoIG9mIHdoaWNoIHRlbGxzIGEgc3RhcnRpbmcgbG9jYXRpb24gTCAoMSAmbHQ7PSBMICZsdDs9IEYpIC0tIEw9MSBpcyB0aGUgZmlyc3QgZmxvd2VyIC0tIGFuZCBhbiBpbnRlcnZhbCBJICgxICZsdDs9IEkgJmx0Oz0gRikgZm9yIHBsYW50aW5nIGZsb3dlcnMuIERlZHVjZSB0aGUgbnVtYmVyIG9mIGVtcHR5IHNsb3RzIHRoYXQgcmVtYWluIGFmdGVyIHBsYW50aW5nIHRoZSBlbnRpcmUgc2V0LjxcL3A+XHJcblxyXG48cD5JZiBCZXRzeSBmb2xsb3dlZCB0aHJvdWdoIG9uIGhlciBpbml0aWFsIHZpc2lvbiwgc2hlIG1pZ2h0IHNwZWNpZnkgdGhlIHBsYW50aW5nIGFzOjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgICAzMCAzICAgICBbMzAgc2xvdHMgdG90YWw7IDMga2luZHMgb2YgZmxvd2Vyc11cclxuICAgICAgMSAzICAgICAgW3N0YXJ0IGF0IHNsb3QgMSBhbmQgcGxhbnQgcm9zZXMgZXZlcnkgM3JkIHNsb3RdXHJcbiAgICAgIDMgNyAgICAgIFtzdGFydCBhdCBzbG90IDMgYW5kIHBsYW50IGJlZ29uaWFzIGV2ZXJ5IDdyZCBzbG90XVxyXG4gICAgICAxIDQgICAgICBbc3RhcnQgYXQgc2xvdCAxIGFuZCBwbGFudCBkYWlzaWVzIGluIGV2ZXJ5IDR0aCBzbG90XTxcL3ByZT5cclxuXHJcbjxwPlRodXMsIHRoZSBlbXB0eSBnYXJkZW4gbG9va3MgbGlrZSB0aGlzOjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgIC4gLiAuIC4gLiAuIC4gLiAuIC4gLiAuIC4gLiAuIC4gLiAuIC4gLiAuIC4gLiAuIC4gLiAuIC4gLiAuPFwvcHJlPlxyXG5cclxuPHA+VGhlbiwgYWZ0ZXIgdGhlIHJvc2UgcGxhbnRpbmc6PFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgICAgUiAuIC4gUiAuIC4gUiAuIC4gUiAuIC4gUiAuIC4gUiAuIC4gUiAuIC4gUiAuIC4gUiAuIC4gUiAuIC48XC9wcmU+XHJcblxyXG48cD5UaGVuLCBhZnRlciB0aGUgYmVnb25pYSBwbGFudGluZzo8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICBSIC4gQiBSIC4gLiBSIC4gLiBSIC4gLiBSIC4gLiBSIEIgLiBSIC4gLiBSIC4gQiBSIC4gLiBSIC4gLjxcL3ByZT5cclxuXHJcbjxwPlRoZW4sIGFmdGVyIHRoZSBkYWlzeSBwbGFudGluZzo8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICBSIC4gQiBSIEQgLiBSIC4gRCBSIC4gLiBSIC4gLiBSIEIgLiBSIC4gRCBSIC4gQiBSIC4gLiBSIEQgLjxcL3ByZT5cclxuXHJcbjxwPjEzIGVtcHR5IHNsb3RzIHJlbWFpbiBhZnRlciBhbGwgdGhlIHBsYW50aW5nLjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IEYgYW5kIEs8XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uSysxOiBMaW5lIGogY29udGFpbnMgdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyB0aGF0IHNwZWNpZnkgdGhlIHBsYW50aW5nIG9mIG9uZSBraW5kIG9mIGZsb3dlcjogTF9qIGFuZCBJX2o8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogQSBzaW5nbGUgbGluZSB3aXRoIGEgc2luZ2xlIGludGVnZXIgdGhhdCBpcyB0aGUgbnVtYmVyIG9mIGVtcHR5IGZsb3dlciBzbG90cyB0aGF0IHJlbWFpbiBhZnRlciB0aGUgcGxhbnRpbmcgaXMgY29tcGxldGU8XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=