Description

At the end of a busy month, N customers are waiting at a bank. There are M counters, and each counter takes a different amount of time to serve one customer. When a counter is free, the first waiting customer goes to that counter. Find the minimum time required to serve all customers.

Input

Output

Constraints

• •1 <= N <= 1,000,000,000
• •1 <= M (number of counters) <= 100,000
• •1 <= processing time per counter <= 1,000,000,000

Examples

6
[7, 10]

28