짜증 난 동료들

면접 대비

시간 제한2초메모리 제한1024 MB

요약

도움 요청을 h번 채워야 할 때, 짜증 수치가 a에서 시작해 요청마다 d씩 오르는 동료들 가운데 최대 짜증 수치의 최솟값을 구합니다.

난이도: 보통10점 중 5점
유형: 이분 탐색, 수학, 그리디
정답자: 아직 제출이 없습니다

문제

일하지 않고 있는 당신의 그림. 출처: XKCD 303

오늘도 사무실의 평범한 하루다. 당신은 자기 일은 하지 않는 데 능한 사람이다. 그래서 동료들에게 "도와달라"고 부탁하지만, 실은 모든 일을 그들에게 시킨다.

동료는 당신을 도와줄수록 짜증이 커진다. 당신은 도움을 요청할 때마다 동료의 짜증이 얼마나 더 커지는지도 알아냈다. 하루의 시작에 동료가 당신에게 가진 짜증 수치는 $a$ 이다. 이것이 그 동료의 초기 짜증 수치다. 도움을 요청할 때마다 짜증 수치는 일정하게 $d$ 만큼 증가하여, $a=a+d$ 가 된다.

당신은 동료들의 도움만으로 $h$ 개의 작업으로 이루어진 프로젝트를 끝내려 한다. 다만 어느 동료도 지나치게 짜증나게 해서는 안 된다.

당신이 할 수 있는 최선은 무엇인가?

입력

첫 줄에 정수 $h$ 와 $c$ 가 주어진다. $h$ ( $1 \le h \le 100\,000$ )는 프로젝트를 완료하기 위해 도움을 요청해야 하는 횟수이고, $c$ ( $1 \le c \le 100\,000$ )는 동료의 수이다.

이어지는 $c$ 개의 줄에는 양의 정수 $a$ 와 $d$ 가 한 쌍씩 주어진다. 이는 초기 짜증 수치가 $a$ 이고, 도움을 요청할 때마다 짜증 수치가 $d$ 만큼 증가하는 동료를 나타낸다 ( $1 \le a, d \le 10^9$ ).

출력

최적 전략을 써서 짜증 수치의 최댓값을 가능한 한 작게 만들었을 때, 그 최댓값을 하나의 수로 출력한다.

예제3

예제 1
입력
```
4 4
1 2
2 3
3 4
4 5
```
예상 출력
```
7
```
예제 2
입력
```
3 2
1 1000
1000 1
```
예상 출력
```
1002
```
예제 3
입력
```
5 2
1 1
2 2
```
예상 출력
```
5
```