카누

면접 대비

시간 제한1초메모리 제한128 MB

요약

카누의 최대 무게와 각 참가자의 몸무게가 주어질 때, 모든 사람을 태우는 데 필요한 최소 카누 수를 구한다.

난이도: 보통10점 중 4점
유형: 그리디, 투 포인터, 정렬, 배열
정답자: 아직 제출이 없습니다

문제

카누 투어를 준비하고 있습니다. 카누는 선착장에서 빌릴 수 있으며 모든 카누는 동일합니다. 카누 한 대에는 최대 두 명까지 탈 수 있고, 함께 탄 사람들의 몸무게 합은 정해진 최대 무게를 넘을 수 없습니다. 비용을 최소로 하려면 모든 참가자를 가능한 한 적은 수의 카누에 나누어 태워야 합니다.

다음을 수행하는 프로그램을 작성하세요.

표준 입력에서 카누 한 대에 탈 수 있는 최대 무게, 참가자 수, 그리고 각 참가자의 몸무게를 읽습니다.
규칙에 따라 모든 참가자를 태우는 데 필요한 카누의 최소 개수를 구합니다.
그 결과를 표준 출력에 씁니다.

입력

첫째 줄에 카누 한 대에 탈 수 있는 최대 무게 $w$ 가 주어집니다 ( $80 \le w \le 200$ ). 둘째 줄에 참가자 수 $n$ 이 주어집니다 ( $1 \le n \le 30000$ ).

이어지는 $n$ 개의 줄에는 각 참가자의 몸무게가 한 줄에 하나씩 주어지며, 각 몸무게는 $5$ 이상 $w$ 이하의 정수입니다.

출력

빌려야 하는 카누의 최소 개수를 첫째 줄에 정수 하나로 출력합니다.

예제1

예제 1
입력
```
100
9
90
20
20
30
50
60
70
80
90
```
예상 출력
```
6
```