부서진 케이크

면접 대비

시간 제한10초메모리 제한512 MB

요약

케이크의 너비와 조각난 직사각형 조각들의 크기가 주어질 때, 조각 넓이의 합을 너비로 나누어 케이크의 길이를 구한다.

난이도: 쉬움10점 중 2점
유형: 수학, 구현, 배열, 완전 탐색
정답자: 아직 제출이 없습니다

문제

부서진 케이크

직사각형 케이크를 트럭에 싣고 식당으로 옮긴다. 가는 길에 트럭이 도로 구멍에 빠지면서 케이크가 완전한 직사각형 조각 $N$ 개로 부서졌다. $i$ 번째 조각의 가로 길이는 $w_i$ , 세로 길이는 $l_i$ 이다 ( $1 \le i \le N$ ).

식당에 도착한 손님은 크기가 같은 케이크를 새로 주문하기로 했다. 그런데 원래 주문서를 끝까지 채우지 않아서 케이크의 가로 길이 $W$ 만 남아 있다. 다행히 부서진 조각은 하나도 잃어버리지 않았다. 조각의 넓이를 모두 더하면 원래 케이크의 넓이와 같다. 케이크의 세로 길이 $L$ 을 구하라.

조각은 부서지면서 방향이 바뀌었을 수 있다. 즉 $w_i$ 가 $W$ 보다 클 수도 있다.

입력

첫째 줄에 케이크의 가로 길이 $W$ 가 주어진다.

둘째 줄에 부서진 조각의 개수 $N$ 이 주어진다.

이어지는 $N$ 개 줄에는 각 조각의 가로 길이 $w_i$ 와 세로 길이 $l_i$ 가 공백을 사이에 두고 주어진다.

제한

$1 \le N \le 5\,000\,000$
$1 \le W, L \le 10\,000$
$1 \le w_i, l_i \le 10\,000$ ( $1 \le i \le N$ )

출력

케이크의 세로 길이 $L$ 을 정수로 한 줄에 출력한다.

예제7

예제 1
입력
```
4
7
2 3
1 4
1 2
1 2
2 2
2 2
2 1
```
예상 출력
```
6
```
예제 2
입력
```
1
1
1 1
```
예상 출력
```
1
```
예제 3
입력
```
10000
1
10000 10000
```
예상 출력
```
10000
```
예제 4
입력
```
1
2
1 4000
1 6000
```
예상 출력
```
10000
```
예제 5
입력
```
3
6
1 1
1 1
1 1
1 1
1 1
1 1
```
예상 출력
```
2
```
예제 6
입력
```
2
2
5 1
5 1
```
예상 출력
```
5
```

예제 7

입력

예상 출력