b035.D. 海加爾山之戰

http://zerojudge.tw/ShowProblem?problemid=b035

內容 ：

這是 Warcraft Ⅲ 劇情模式最後一場戰鬥，人類、獸人和夜精靈團結起來保護世界之樹，抵擋燃燒軍團的入侵。各個種族的軍隊聚集在海加爾山的山腳下，靈可能的加強世界之樹的防禦工事，同時夜精靈的首領 Malfurion 在山頂準備釋放最古老的世界之樹 Nordrassil 的力量，一口氣消滅燃燒軍團。

玩家的任務就是在山下盡可能的拖延時間，讓 Malfurion 成功釋放出Nordrassil 的怒火。這天，Archimonde 率領著燃燒軍團追著人類的首領Jaina來到了一座森林。這座森林是人類的基地，裡面蓋了 n 座城堡。Jaina 計畫在這裡拖慢 Archimonde 前進的速度，方法很簡單：讓 Jaina 的軍隊被 Archimonde 追著，一邊放棄城堡一邊撤退，到最後沒路走了就用Jaina 的傳送術帶大家飛到獸人的基地。執行戰術的時候只有一點要注意：被 Archimonde 走過的地方會變成腐地，馬上會被後面的燃燒軍團佔領，不能再回去了。如前面所提到的，目標是拖時間，所以希望讓 Archimonde 佔領越多城堡越好。Jaina 看著手上的地圖，暗自計算著擋得了多久...

山下的城堡都是正方形的，Archimonde 佔領一座城堡大約需要和城堡面積相同的時間，因此佔領一座邊長為 3 的城堡大約要 9 個小時。

輸入說明 ：

輸入檔包含多組測試資料，每組測試資料的第一行有一個數字 n，表示有n（1 ≦ n ≦ 5000）座城堡。下一行每行有 n 個數字每座城堡的邊長，介於 1 到 100 之間。讀到 n = 0 的時候代表測試檔案的結尾，不需要對於這個數字作任何輸出。

輸出說明 ：

對每組測試資料，輸出一個數字表示 Archimonde 大約需要幾個小時才能佔領每座城堡。

範例輸入 ：

若題目沒有特別說明，則應該以多測資的方式讀取，若不知如何讀取請參考 a001 的範例程式。

5 1 2 3 4 5 0

範例輸出 ：

55

提示 ：

出處 ：

2006 NPSC 國中組決賽