Challenge: Reading Plan

Lab Java Intermediate 20 points

A book has n chapters with given page counts, read in order. You must finish in d days and you never split a chapter across days. What is the smallest number of pages per day that makes it possible? Binary search on the answer: for a guessed limit, count the days greedily.

Input

Line 1: n d (1 ≤ d ≤ n). Line 2: n page counts.

Output

The smallest daily page limit.

Example

Input

5 3
30 20 50 10 40

Output

Sample input available Sample output available

Editor

Java

Hints

The answer is between the biggest chapter and the total of all pages.

For a limit, fill each day until the next chapter won't fit. If that needs ≤ d days, the limit works – try smaller.

Solution explanation

Checking one limit is O(n), and binary search tries about log(total pages) limits: O(n log S). Trying every limit one by one would be far slower.

Show solution

import java.util.Scanner;

public class Main {
    static int daysNeeded(int[] pages, long limit) {
        int days = 1;
        long today = 0;
        for (int p : pages) {
            if (today + p > limit) {   // doesn't fit: start a new day
                days++;
                today = 0;
            }
            today += p;
        }
        return days;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), d = sc.nextInt();
        int[] pages = new int[n];
        long lo = 0, hi = 0;
        for (int i = 0; i < n; i++) {
            pages[i] = sc.nextInt();
            lo = Math.max(lo, pages[i]);   // must fit the biggest chapter
            hi += pages[i];                // one day for everything always works
        }
        long answer = hi;
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            if (daysNeeded(pages, mid) <= d) {
                answer = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        System.out.println(answer);
    }
}

Output

Answer