時間制限 : sec, メモリ制限 : KB
Japanese

C : 壺 / Pots

問題文

ここに 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 ≤ N ≤ 200
  • 1 ≤ M ≤ 200
  • 1 ≤ K_i ≤ 20
  • 1 ≤ S_{ij} ≤ 20
  • 1 ≤ H_{ij} ≤ 20

出力

答えを 1 行で出力せよ. 0.00001 以下の絶対誤差を含んでも良い.

サンプル

サンプル入力1

2 15
2 3 3 7 2
2 7 1 1 4

サンプル出力1

6.33333333

サンプル入力2

2 14
1 2 4
2 5 2 1 4

サンプル出力2

6
サンプル 1, 2 の入出力を図示すると次のようになる.

サンプル入力3

2 25
4 8 9 1 9 6 5 2 8
4 1 7 4 4 1 6 4 3

サンプル出力3

13

Note

Commentary