【問題G24】過橋。            [回前頁]

台大聯誼會舉辦活動，邀請歷屆校友組成海外旅行團。一日，因為交通因素，眾人來到目的地時已經夜深，只有一盞油燈照明，並且要過一條窄橋才能到河對岸的旅館。由於團員老少體能不一，過橋所需的時間不盡相同，走得快的年輕人必須放慢腳步，和同行的長輩一起使用油燈到達彼岸，若是一趟走不完所有的人，則要派一個人把油燈提回來。油燈的燃料有限，若是過橋的先後順序不能妥善安排，可能人還沒走完燈就熄了。請你根據輸入檔的資料，計算出妥善的安排下，最快多少時間所有團員可以安全過橋。

輸入檔說明

輸入檔案中有多組測試資料。每組測試資料的第一行有兩個整數n和m，表示總共有n個人過橋，一次最多只能走m個人，且1 £ n, m £ 16。第二行有n個正整數，分別表示每個人過橋所需的時間，且不大於1000。在檔案的最後，以兩個0表示結束。各組測試均有解，即m等於1時，n也會等於1。

輸出檔說明

每一組測試資料，都輸出一個整數，表示團員全數過橋所需的最少時間。請每行輸出一組測試資料的答案。

範例輸入

範例輸出

提示

我們可以證明加入以下的條件，並不會增加全數團員過橋的時間︰

1.到達對岸後，僅派一個人把燈提回來。

2.不論往那一個方向，若派出的人數小於m，這些人一定是該岸邊走得最快的。