## Delivery Capacity

Points: 100
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
C, C++, Java, Python

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: , 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

• commented on June 5, 2021, 8:30 p.m.

Question should mention he had to deliver in given order.

• commented on June 13, 2021, 8:06 p.m.

This comment saved me.