盩僰麌最近迷上了叫作ニュー・スーパーフックガール的遊戲，但是他常常對他的成績不太滿意，於是他決定採取一種策略來練習這個遊戲裡的每個關卡。

這個遊戲一共有$N$個關卡，由0編號到$N-1$。每一關盩僰麌需要1單位的時間去練習以獲得他想要的成績。他認為分段練習是最好的方法，於是他把這些關卡分成$k$個階段，使得每一段裡的關卡的編號都連續。

盩僰麌對分段練習有特殊的堅持，他並不只是單純的把每個關卡都刷過一次而已。盩僰麌寫了一個程式，協助他挑選接下來要練習哪一關。
對於每個階段，當這個階段中每一個關卡都練習完了之後，盩僰麌就會練習下一個階段，重複直到每個階段的每個關卡都練習完畢。

而盩僰麌寫的程式的運作方式如下：假設盩僰麌現在練習的階段中，盩僰麌已經練習過的關卡編號是$a_1,a_2,...,a_x$，而還沒練習過且編號最低的關卡編號是$b$，則這個程式會計算出$C=t_b+t_{a_1}+t_{a_2}+\cdots+t_{a_X}$，然後隨機決定它的輸出：$\frac{t_b}{C}$的機率會輸出編號$b$的關卡、$\frac{t_{a_1}}{C}$的機率會輸出編號$a_1$的關卡，以此類推。

不過因為不久後就要舉行這個遊戲的比賽了，請幫盩僰麌算出，如果按照他的這個練習方法，對於每種階段的劃分方法，練習完這個遊戲的期望時間最短可以到多少。

For Testdata: 0 ~ 11, Score: 8
For Testdata: 0 ~ 28, Score: 14
For Testdata: 0 ~ 41, Score: 32
For Testdata: 42 ~ 54, Score: 56
For Testdata: 0 ~ 72, Score: 90