きつねのしえるはうなぎを食べるのが好きである.
2T+1 枚の鉄板が連続して並んでおり,順番に -T, -T+1, ..., T の番号が付いている.しえるはこれらの鉄板に熱を加え,生きたうなぎを焼こうとしている.うなぎを焼く手順は以下のようなものである.
ところで生きたうなぎというのはとても活きがよくさらに頭も良いので,もしかすると自分にかかる熱さの総和が最小になるように動いたりするんではないかとしえるは不安になった.そうなると鉄板に適当に熱を加えただけではうなぎを十分に加熱できない恐れさえある.
そこであなたには,うなぎが常に最適に動くとして,うなぎに与えることのできる熱さの和の最大値を求めて欲しい.
入力は以下の形式で与えられる.
T E C(-T) C(-T+1) ... C(T)T はうなぎを熱する時間,E は鉄板に与えることの出来るエネルギーの総和,C(i) は i 番の鉄板の比熱である.
1 行目にうなぎに与えられる熱さの和の最大値を出力せよ.小数点以下何桁でも出力して構わないが,相対誤差あるいは絶対誤差が 10-6 未満になっていなければならない.
1 100 1 1 1
100.0
この場合は 0 番の鉄板にエネルギーを全て加えるのが最適である.
2 100 1 2 100 2 1
2.8301886792453
5 100000 99999 99999 99999 1 1000 1000 1000 1 99999 99999 99999
199.4680851063830