這個寒假我們打算來個阿帕拉契山脈登山之旅，整條阿帕拉契山脈的登山路線從喬治亞州的斯普林吉爾山開始，綿延至東北方緬因州的塔卡丁山，全長共2160英哩。雖然我們只計畫攀登其中的一部分，但是這仍然是我們第一次真正的登山旅行， 相信也是一個絕佳的機會來學習登山技巧。
除此之外，路徑規劃對於這次旅行而言也是很重要的一部分，我們已經知道沿途總共有幾個營區可供野營夜宿，也規劃好這次旅程預計停留K個晚上， 同時，我們也知道兩個相鄰營區間的距離，由於分開行動對於登山者而言是種風險，因此整個團隊同一晚上也必須在同一個營區過夜。我們希望經由以上這些資訊，可以規劃出一個行程，以將我們單一天所需走的最大距離減到最低。
舉例來說，如果我們規劃過夜兩晚（也就是包含三天的路程），那麼如果我們這三天分別需要走9、10、5英哩才能到達當天過夜的營區， 那麼我們這趟旅途中，單一天要走的最大距離就是10英哩；如果我們有另外一個選擇這三天可以分別走9、6、9英哩，則單一天要走的最大距離就是9英哩。在此例中，後者會是我們較想要的行程。
你的任務就是寫一個程式，讀入N個相鄰營區間的距離，在已知停留K個晚上的情況下，找出一個最佳的野營策略，使得單一天所需經過的最大距離為最小。請留意第一個距離代表從出發點到第一個營區的距離，而最後一個距離代表從最後一個營區到目的地的距離。
Input
輸入的資料會包含數個測試個案，每個測試個案會包含以下資料：
測試個案的第一行會有兩個數字，第一個代表總共有幾個營區(0<N<=600)，第二個代表過夜幾個晚上(0<=K<=300)。
接下來的N+1行代表每兩個相鄰營區間的距離。
Output
對每一筆測試個案，輸出一行包含「單一天所需經過的最大距離」的最小值。
Sample Input
4 3 7 2 6 4 5
Sample Output
8