まず，0 の目が出ない様に変換しておく． 0 の個数を \(z\) 個とおく． 0 以外の目が出るまでの回数の期待値は \(\frac{p}{p-z}\) 回． \(c\) を \(c \cdot \frac{p}{p-z}\) で置き換えて，\(z\) を除いたルーレットで考えてよい．
\(e_{x}\) を，スコアが \(x\) のときの コストの最小値の期待値とする． \(x\) に到達するまでの出目は，今後に影響しない．
スコアを固定すると， このときの最善のルーレットの選び方が決まる． (最善とは限らない) ルーレットを選んだとき，どれくらい 寄与するのかを考える．
どのルーレットを使うか選ぶゲームと言える． 基本通り後退解析をするので，スコアが大きいほうから決めていく． スコア \(x\) とルーレット \(i\) を固定する． 出目 \(t\) 毎に \(\frac{e_{x+t}}{\vert s_{i} \vert} \) だけ \(e_{x}\) に寄与する． 1 回ルーレットを回すために \(c_{i}\) コストがかかるので， \(e_{x} = min_{i \in N}(\sum_{t \in s_{i}} \frac{e_{x+t}}{\vert s_{i} \vert} + c_{i})\) となる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,m;
cin >> n >> m;
rep(i,n){
cin >> c[i] >> p[i];
s[i].resize(p[i]);
cinv(s[i]);
ll z = 0;
for(auto t: s[i]) if(t == 0) z++;
c[i] *= p[i]/(double)(p[i] - z);
p[i] -= z;
}
e[m] = 0;
drep(x,m+1){
rep(i,n){
double sum = 0;
for(auto t: s[i]) if(t){
ll y = x+t;
chmin(y, m);
sum += e[y];
}
chmin(e[x], c[i] + sum/p[i]);
}
}
printf("%.10lf\n", e[0]);
return 0;
}
