Given an array $A$ with $n$ elements, find the smallest integer $x$ such that the array $A$ can be divided into exactly $k$ contiguous subarrays, each with a sum not exceeding $x$.
### Input
- The first line contains two integers $n, k$.
- The second line contains $n$ integers $A_i$.
### Output
- Print an integer $x$ as the answer.
### Constraints
- $1 \le k \le n \le 10^5$.
- $1 \le A_i \le 10^9$.
### Sample
Input:
```
5 2
5 4 3 2 1
```
Output:
```
9
```
**Note: A possible division `[5 4] [3 2 1]`. There is no way to divide $A$ if $x$ is smaller than $9$**
