Idle Terminal

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

요약

n개의 작업 시간과 k개의 코어가 주어질 때, 첫 작업 시작부터 마지막 완료까지 완료 메시지 사이의 최대 공백 시간을 구한다.

난이도: 보통10점 중 6점
유형: 힙, 시뮬레이션, 그리디
정답자: 아직 제출이 없습니다

문제

It is migration day at the Big Administration Processing Company: the database containing all administrative documents of all clients needs to be migrated to the latest version of the database software. Quite some things have changed over the past years, and this software has not been upgraded, so the number of migration jobs is high.

The migration jobs run in parallel on the multicore server machine in a first-come-first-serve fashion: every time a core is done running a job, it starts running the first job that has not yet started. The Idle Terminal (IT) Team is sitting huddled around the terminal window, eagerly awaiting the dopamine boost when another migration job completes successfully and a message is printed to the terminal.

The IT Team starts breaking out in sweat when nothing changes on the terminal for quite a long time. Did the connection hang? Has the server soft-locked? Did all jobs get stuck in infinite loops?? On the other hand, some migration jobs really do have a long duration, and it may simply be a coincidence that there are only long-running jobs active at the time. To calm down the IT Team, you decide to compute the longest time that goes by without seeing a new message on the terminal, starting from the moment that the first migration jobs start running.

입력

The input consists of:

One line with two integers $n$ and $k$ ( $1 \leq n, k \leq 10^5$ ), the number of migration jobs and the number of cores in the server machine.
One line with $n$ integers $d$ ( $1 \leq d \leq 100$ ), the duration of each job in the order that they are processed.

예제5

예제 1
입력
```
2 2
3 7
```
예상 출력
```
4
```
예제 2
입력
```
5 10
1 2 3 4 5
```
예상 출력
```
1
```
예제 3
입력
```
4 1
2 10 6 4
```
예상 출력
```
10
```
예제 4
입력
```
6 2
3 5 8 10 4 1
```
예상 출력
```
6
```
예제 5
입력
```
6 3
2 4 6 6 6 6
```
예상 출력
```
2
```