Immigration Inspection

Time limit1sMemory limit128 MB

Summary

Given N counters with per-person processing times and M travelers, find the minimum time to process everyone using binary search on the answer.

Level: Medium4 of 10
Topics: Binary search, Math
Solved: No attempts yet

Problem

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.

Input

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)

Output

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

Examples2

Example 1
Input
```
2 6
7
10
```
Expected output
```
28
```
Example 2
Input
```
7 10
3
8
3
6
9
2
4
```
Expected output
```
8
```