a640. CPE：Winterim Backpacking Trip (UVa 907)

題目描述

你計畫沿步道旅行，途中有 N 個可露營地點，只能在這些地點過夜。已知起點、各營地與終點之間的相鄰距離，希望安排 K 夜，也就是 K + 1 天的行程。

請選擇過夜營地，讓「單日步行距離的最大值」盡可能小。例如每天走 9、10、5 英里時最大值是 10；若改成 9、6、9 英里，最大值降為 9。

輸入格式

輸入包含多組資料，讀到檔案結尾為止。每組先有 N、K，0 < N ≤ 600，0 ≤ K ≤ 300。接著 N + 1 行各有一個相鄰距離。

第一個距離為起點到第一個營地，最後一個為第 N 個營地到終點。

輸出格式

每筆輸出一行，表示最佳安排下的最大單日步行距離。

題目來源：UVa 907 — Winterim Backpacking Trip。 原題：https://onlinejudge.org/external/9/907.pdf