잼버리

면접 대비

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

요약

N개의 물건을 M명의 스카우트에게 한 명당 한두 개씩 나눌 때, 가장 많이 든 사람의 짐 무게가 최소가 되는 값을 구합니다.

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

문제

스카우트 대원들이 다른 스카우트와 함께 큰 모임에 참가하려고 준비하고 있다. 리더 힐데보르그는 스카우트 모토인 Be Prepared의 뜻에 따라, 모험에서 필요할 만한 유용한 물품을 대원들에게 나누어 주려고 한다. 물품마다 크기가 달라서, 최대한 공평하게 나누기 위해 어떤 대원이 가지는 물품 크기의 합을 가능한 한 작게 하려고 한다. 힐데보르그는 한 대원에게 물품을 두 개보다 많이 주지 않으려 한다. 물품이 더 많아지면 대원들이 모든 물품을 챙기기 어려울 것을 걱정하기 때문이다. 물품의 크기가 주어졌을 때, 어떤 대원이 가지는 합의 최댓값이 가질 수 있는 최솟값을 구하시오.

입력

첫 줄에 양의 정수 $N$ 과 $M$ 이 주어진다 ( $1 \leq N \leq 2M$ , $1 \leq M \leq 100$ ). $N$ 은 유용한 물품의 개수이고, $M$ 은 스카우트 대원의 수이다. 둘째 줄에는 물품의 크기를 나타내는 양의 정수 $a_i$ ( $1 \leq a_i \leq 10^7$ )가 $N$ 개 주어진다.

출력

어떤 대원이 가지는 물품 크기의 합의 최솟값을 정수 하나로 출력한다.

예제2

예제 1
입력
```
3 4
10 10 10
```
예상 출력
```
10
```
예제 2
입력
```
5 4
9 12 3 9 10
```
예상 출력
```
12
```