本棚
太郎君はとある小説にはまっています。その小説は全部で n 巻あり、各巻で本の厚さが異なります。太郎君はこの小説が大変気に入ったので、その小説専用の本棚を買おうと思っています。しかし、部屋に大きな本棚を置くとかなり狭くなってしまうので、出来るだけ本棚の幅が小さくなるように工夫しなければなりません。床から天井の高さを測ったところ、どうやら m 段の本棚なら置けることが分かりました。そこで、小説 n 巻をどのように分ければ m 段の本棚の幅を最小に出来るでしょうか? 太郎君にはこだわりがあり、各段に納める小説は巻の番号順に並んでいなければなりません。
本棚の段数、小説の巻数、各本の厚さを入力として、全巻を 1巻から順に収めることができる本棚の中で幅が最小となるものの幅を求めるプログラムを作成してください。ただし、本棚の枠の大きさは幅に含めないこととします。
Input
複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。各データセットは以下の形式で与えられます。
m n w1 w2 : wn
１行目に部屋に置くことができる本棚の段数 m (1 ≤ m ≤ 20)、 小説の巻数 n (1 ≤ n ≤ 100) が与えられます。続く n 行に第 i 巻の本の厚さを表す整数 wi (1 ≤ wi ≤ 1000000) が与えられます。
ただし、本棚の幅は 1500000 を超えないものとします。
データセットの数は 50 を超えません。
Output
データセット毎に最小となる本棚の幅を１行に出力します。
Sample Input
3 9 500 300 800 200 100 600 900 700 400 4 3 1000 1000 1000 0 0
Output for the Sample Input
1800 1000