## D days Job Scheduler

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

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

You work at a multinational corporation. Deadlines are taken way too seriously, i.e., if you are given a job with a deadline of D days, you must complete the job in exactly D days and you must complete at least one task in a day. But every task is not of the same difficulty.

Being a lazy person, you want to complete the job in the most effortless way possible. Let's say you want to complete three tasks in a day with difficulties as [4,1,2], then the effort required to complete these tasks is the maximum of all tasks, i.e., 4. In other words, let's say you decide to do X tasks in a day with $$d_1, d_2, ..., d_x$$ difficulties, the effort required to complete these tasks is maximum($$d_1, d_2, ..., d_x$$)

You need to find the minimum effort required to complete all the tasks.

#### Input

The first line contains two integers, N and D. N represents the number of tasks, D represents the number of days.

Second line contains N integers -- $$d_1, d_2, d_3, ..., d_n$$

#### Output

An integer, the minimum effort required.

#### Constraints

$$1 \leq N \leq 300$$

$$1 \leq D \leq 10$$

$$0 \leq d_i \leq 1000$$

$$D \leq N$$

##### Example

Input

8 2
1 2 3 4 5 6 7 8

Output

9

Explanation do the first task on Day1 and the rest of the tasks on Day2. (1 + 8) = 9

If we try to do all the tasks on day 1, the answer would be 8, but the conditions say that you have to do at least one task in a day, so there will be no tasks on day2. Hence it can not 8.

## Comments

• commented on June 8, 2021, 9:26 p.m.

Can someone provide few more test cases if possible

• commented on June 9, 2021, 12:11 p.m.

7 3 5 7 9 1 2 11 15 i guess the answer for this should be 25 {5,7,9} in one day {1} in one day and the remaining in the last day which results in a total effort of 25

• commented on May 23, 2021, 10:48 p.m.

Should the order of task is same or we can do any task on any day?

• commented on May 24, 2021, 1:54 a.m.

Yes, the order should be maintain, You cann't perform (i+1)th task before ith task. Either you can finish ith task before (i+1)th task or do both on the same day.

• commented on May 23, 2021, 10:22 p.m.

When we have 0 difficulty then we have to include it in our day task or not. given range is 0≤ di ≤1000.

• commented on May 24, 2021, 1:54 a.m.

Yes, it will be a valid task with zero diificulty