Demux Problems Submissions Users Contests Log in Sign up


D days Job Scheduler


Submit solution

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


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

    Can someone provide few more test cases if possible


    • 0
      Kushal  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


  • 1
    KekriCoder  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?


    • 0
      Rajat_122  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.


  • 0
    KekriCoder  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.


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

      Yes, it will be a valid task with zero diificulty