Demux Problems Submissions Users Contests Log in Sign up


Delivery Capacity


Submit solution

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


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

    Question should mention he had to deliver in given order.