动态规划，主要是用单调性求区间的最小期望。
代码如下：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#define MAX 1004
#define inf 1<<22
using namespace std;
double dp[MAX][MAX],b,add,l,r;
map<int,double>q;
struct node
{
int x;
double p;
}an[MAX];
void init(int m)
{
int i,j;
for(i=;i<=;i++)
for(j=;j<=;j++)
dp[i][j]=inf;
for(i=;i<=m;i++)
for(j=i;j<=m;j++)
dp[i][j]=0.0;
}
int main(){
int n,m,k,i,j,a;
while(scanf("%d%d",&n,&m)&&(n+m)){
q.clear();
for(i=;i<n;i++){
scanf("%d",&k);
for(j=;j<k;j++){
scanf("%d%lf",&a,&b);
q[a]+=b;
}
}
n=;
for(map<int,double>::iterator it=q.begin();it!=q.end();it++){
an[++n].x=it->first;
an[n].p=it->second;
}
init(m);
for(i=;i<=n;i++){
for(j=;j<=m&&j<=i;j++){
dp[i][j]=inf;
double pre=0.0,suf=0.0;
int cur=i;add=0.0;
for(k=i-;k>=j-;k--){
if(k+!=i){
pre+=an[k+].p;
add+=an[k+].p*(an[cur].x-an[k+].x);
}
while(an[cur].p+suf<pre){
suf+=an[cur].p;
cur--;
pre-=an[cur].p;
int t=an[cur+].x-an[cur].x;
add-=an[cur].p*t;
add+=an[cur+].p*t;
add-=pre*t;
add+=(suf-an[cur+].p)*t;
}
dp[i][j]=min(dp[i][j],dp[k][j-]+add);
}
}
}
printf("%.2lf\n",dp[n][m]);
}
return ;
}