용돈 관리

현우는 용돈을 효율적으로 쓰기 위해 계획을 세우려고 한다. 앞으로 $N$일 동안 매일 사용할 금액이 정해져 있고, 현우는 통장에서 돈을 빼서 쓰되 인출하는 횟수를 정확히 $M$번으로 하려고 한다.

현우는 통장에서 한 번에 $K$원을 인출한다. 지금 가진 돈으로 그날 필요한 금액을 낼 수 있으면 그대로 쓰고, 남은 돈은 다음 날로 넘긴다. 만약 가진 돈이 그날 필요한 금액보다 적으면, 남은 돈을 다시 통장에 넣은 뒤 새로 $K$원을 인출하고 그날 금액을 낸다.

또한 현우는 숫자 $M$을 좋아해서 인출 횟수를 정확히 $M$번으로 맞추고 싶어 한다. 그래서 가진 돈이 그날 필요한 금액보다 많더라도, 원한다면 남은 돈을 통장에 넣고 다시 $K$원을 인출할 수 있다. 즉, 꼭 필요한 최소 인출 횟수가 $M$ 이하이기만 하면 추가 인출을 끼워 넣어 정확히 $M$번을 맞출 수 있다.

현우는 돈을 아끼기 위해 인출 금액 $K$를 최소로 하려고 한다. $N$일을 모두 보내면서 인출을 정확히 $M$번 할 수 있는 가장 작은 $K$를 구하는 프로그램을 작성하시오.

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. ($1 \le N \le 100{,}000$, $1 \le M \le N$)

둘째 줄부터 $N$개의 줄에 걸쳐, $i$번째 날에 현우가 사용할 금액이 한 줄에 하나씩 주어진다. ($1 \le$ 금액 $\le 10{,}000$)

첫째 줄에 현우가 통장에서 인출해야 하는 최소 금액 $K$를 출력한다.