## Delivery Capacity

Kamaraj works for zomato and has to deliver `n`

items.
All the items have differnt weights, weight of \(i^{th}\) item is denoted by \(w_i\).

He has to complete all these deliveries within `d`

days, or his boss will fire him.

Kamaraj decides to complete multiple deliveries in a day, inorder to achieve the target.

He delivers items in a sack, a particular sack can only carry at max `x`

weight.

Help him decide minimum `x`

required to complete the job.

For more clarity, see sample examples.

#### Input

The first line contains two integers -- `n`

and `d`

The second line contains n integers -- \(w_1, w_2, ..., w_n\)

#### Output

An integer `x`

-- minimum weight of sack, he should carry

#### Constraints

\(1 \leq \) `n`

\(\leq 5.10^4\)

\(1 \leq \) `d`

\(\leq n\)

\(1 \leq \) \(w_i\) \(\leq 500\)

#### Example

**Input**

```
2 1
11 8
```

**Output**

`19`

**Explanation**

As he has to complete all deliveries in one day: 11 + 8 = 19

**Input**

```
8 4
19 3 18 18 5 5 11 17
```

**Output**

`28`

**Explanation**

- Day 1: [19, 3], total weight = 22 \(\leq\) 28
- Day 2: [18], total weight = 18 \(\leq\) 28
- Day 3: [18, 5, 5], total weight = 28 \(\leq\) 28
- Day 4: [11, 17], total weight = 28 \(\leq\) 28

If we use a sack whose capacity is less than 28, then the job can never be done in 4 days.

## Comments

Question should mention he had to deliver in given order.

This comment saved me.