콘센트

면접 대비

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

요약

N개 기기의 충전 시간과 M개의 동일한 콘센트가 주어질 때, 기기가 한 번에 콘센트 하나만 쓰는 조건에서 모든 기기를 충전하는 최소 시간을 구한다.

문제

광재는 전자기기 대여사업을 시작했다. 퇴근하기 전에 다음날 손님들에게 빌려줄 N개의 전자기기를 충전하려 한다. 사용 가능한 콘센트는 M개가 있고, 성능은 모두 동일하다.

전자기기들은 한 번에 하나의 콘센트에서만 충전이 가능하고, 충전에 필요한 시간은 2k(0 ≤ k ≤ 15, k는 정수) 형태이다.

광재의 빠른 퇴근을 위해 모든 전자기기를 충전하기 위한 최소 시간이 얼마인지 알려주자.

첫째 줄에 전자기기의 개수 N과 콘센트의 개수 M이 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10)

둘째 줄에 충전에 필요한 시간 ti를 나타내는 N개의 정수가 주어진다. (20 ≤ t**i ≤ 215, ti = 2k (0 ≤ k ≤ 15, k는 정수))

충전에 필요한 최소 시간을 출력한다.