초콜릿 먹기

Bessie가 초콜릿 $N$개($1 \le N \le 50000$)를 받았습니다. 하지만 너무 빨리 먹고 싶지는 않아서, 앞으로 $D$일($1 \le D \le 50000$) 동안 먹을 계획을 세워 그 기간의 하루하루 행복도 중 최솟값을 최대로 만들고자 합니다.

Bessie의 행복도는 정수이며 $0$에서 시작합니다. 잠을 자는 매일 밤마다 행복도는 절반으로 줄어들며, 나누어떨어지지 않으면 내림합니다. $i$번째 초콜릿을 먹으면 행복도가 정수 $H_i$($1 \le H_i \le 1000000$)만큼 증가합니다. 어떤 날에 초콜릿을 하나 이상 먹었다면, 그날의 행복도는 초콜릿을 모두 먹은 뒤의 값(잠들기 직전의 행복도)으로 봅니다. Bessie는 받은 순서대로만 초콜릿을 먹을 수 있으며, 하루에 초콜릿을 몇 개든(0개 포함) 먹을 수 있습니다.

예를 들어 행복도가 각각 $(10, 40, 13, 22, 7)$인 초콜릿 $5$개를 $5$일에 걸쳐 먹는다고 합시다. 다음은 최적인 한 가지 계획에서의 하루별 행복도입니다.

여기서 취침 시 행복도의 최솟값은 $24$이며, 어떤 계획으로도 이 최솟값을 더 크게 만들 수 없으므로 정답은 $24$입니다.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $D$.
• 둘째 줄부터 $N+1$째 줄까지: $i+1$째 줄에 정수 $H_i$가 하나 주어집니다.

• 한 정수를 출력합니다: $D$일 동안 Bessie의 취침 시 행복도의 최솟값이 가질 수 있는 가장 큰 값.