Jamboree

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

요약

N개의 물건 크기를 M명의 스카우트에게 최대 두 개씩 나눠 줄 때, 한 사람이 드는 최대 합을 최소로 만든다.

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

문제

A group of scouts are preparing to go to a large meeting with other scouts. Their leader Hildeborg, in spirit of the scout motto "be prepared", wants to distribute some useful items among the scouts that they most probably will need on their adventure. The items come in different sizes, so to make this as fair as possible, she wants to make sure that the total size of items carried by any scout is as small as possible. Furthermore, Hildeborg does not want to give more than two items to any scout as she is afraid that it otherwise will be too hard for them to remember to bring everything. Given the sizes of the items, what is the least maximum total size, computed as the sum of items, any scout will have to carry?

입력

The first line of input contains two positive integers $N$ and $M$ ( $1 \leq N \leq 2M$ , $1 \leq M \leq 100$ ). $N$ is the number of useful items, and $M$ is the number of scouts. The second line contains $N$ positive integers $a\_i$ ( $1 \leq a\_i\leq 10^7$ ) giving the sizes of the items.

출력

Print one integer, the smallest total size that any scout has to carry.

예제2

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