TopCoder

Thumb   5
Y(OwO)Y
真実より 優しい嘘をプリーズ

User's AC Ratio

95.0% (38/40)

Submission's AC Ratio

39.7% (58/146)

Description

骨牌是一片片長方形的塑膠牌,可以將它立起來排成你想要的圖案,加上骨牌本身會有顏色的變化,所以在壓下骨牌後,骨牌一塊塊倒下,就可以展現出美麗的圖案.但是在排骨牌的過程中,常常會有不小心壓到的時候,導致辛苦的結果都不見了.所以有人發明了一種很重的骨牌,在必要的地方把關,防止在你不小心壓下骨牌後,造成的結果會很慘,因為它有足夠的重量,不會倒下,讓傷害停在這裡.

然而我們所擁有的很重骨牌只有幾個,只能在真的非常重要的地方把關,每一個地方會用一個正整數(cost)表示,定義為它排好所需的時間,需要越長,代表重排也要越久,也就越重要.於是我們必須善用這些很重的骨牌,讓傷害降到最小,我們將最大傷害強度定義為,碰倒任一張骨牌之後(可能向前倒或向後倒),可能需要重排的cost總和的最大值.

Input Format

w個很重的骨牌,n條排好的骨牌列,每一列的cost按照順序排好,形式如下

n w
s1 s2 ... sn

也許會有很多組,讀到w和n都是0的時候結束,不需對這一組做輸出
(w和n和s1,s2 ... sn都為小於1001的正整數)

Output Format

min

min為在你安排好很重骨牌的位置後,讓最大傷害強度降到最低的值

Sample Input

3 1
2 3 5
0 0

Sample Output

5

Hints

由於3 1那一組可以將一個很重的骨牌放在 2 前, 2 3間, 3 5間, 5後,其中2前的最大傷害強度為10 , 2 3間的最大傷害強度為 8 , 3 5間的最大傷害強度為5 , 5後的最大傷害強度為10,所以把重骨牌放在3 5間做保護會得到最好的結果min(10,8,5,10)=5,因此最後min為5

Problem Source

原TIOJ1432 / NPSC2004初賽(prob B)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536