##Title Description

The interstellar transport ship needs to transport n containers containing rare minerals to k space stations. Each container has a value of $a_i$ and must be loaded continuously into different transport compartments in order. To prevent overloading of individual compartments, it is necessary to design an allocation scheme that minimizes the maximum cargo capacity among all compartments.

Input format

The first line consists of two integers, $n$ and $k (1\le k\le n\le 1e5)$

The second line contains $n$ integers representing $a_i (1 \le a_i\le 1e4)$

Output format

Minimum and maximum achievable cargo capacity

Example

5 3
4 2 4 5 1

6