ここに N 個の不思議な形の壺がある. i 番目の壺は K_i 個の直円柱を下から順に鉛直に繋げた形状である. 繋がっている順番は変えることができない. A 氏は体積 M の水を持っている. この水をそれぞれの壺に好きな量ずつに分けて注ぐ. 水が全く入っていない壺が存在しても構わない. また,全ての壺が水で満たされたとき,それ以上水を注ぐ事はできない.それぞれの壺の水面の高さの総和の最大値を求めよ.
N \ M K_1 \ S_{11} \ H_{11} \ … \ S_{1 K_1} \ H_{1 K_1} K_2 \ S_{21} \ H_{21} \ … \ S_{2 K_2} \ H_{2 K_2} … K_N \ S_{N1} \ H_{N1} \ … \ S_{N K_N} \ H_{N K_N}
1 行目に N, M が, 1+i 行目には i 番目の壺の情報が入力される. K_i は直円柱の数であり,S_{ij}, H_{ij} はそれぞれ壺を構成する下から j 番目の直円柱の底面積と高さである.
答えを 1 行で出力せよ. 0.00001 以下の絶対誤差を含んでも良い.
2 15 2 3 3 7 2 2 7 1 1 4
6.33333333
2 14 1 2 4 2 5 2 1 4
6サンプル 1, 2 の入出力を図示すると次のようになる.
2 25 4 8 9 1 9 6 5 2 8 4 1 7 4 4 1 6 4 3
13