Immigration Inspection

M travelers are waiting in one line for immigration inspection. There are N inspection counters, and counter k takes Tk seconds to process one traveler.

Initially, every counter is empty and ready. A counter can process only one person at a time. The first person in line may move to any empty counter, but they do not have to move immediately; they may wait for a faster counter to become available.

Compute the minimum time required until all travelers have completed inspection.

The first line contains N and M. (1 <= N <= 100,000, 1 <= M <= 1,000,000,000)

Each of the next N lines contains Tk, the time in seconds that one counter takes to process one traveler. (1 <= Tk <= 1,000,000,000)

Print the minimum time required for all travelers to complete inspection.