从源点向每个点连接容量为该点人数，费用为1的边，
把原图中的每条边拆成两条，一条容量为1，费用为1，另一条容量为ci-1，费用为1-pi
从每个点向汇点连接容量为该点面包数量，费用为1的边。
跑的费用流为按照乘积跑个最大费用流。
可以取个对数，乘法变成加法，
可以再取个负数，最大费用变成最小费用。
别忘了最后还原回来。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
#define E 2.71828182845904523536
#define EPS 0.00000001
#define MAXN 201
#define MAXM 25001
#define INF 2147483647
int S,T;
int en,u[MAXM],v[MAXM],first[MAXN],__next[MAXM],cap[MAXM];
double cost[MAXM];//__next Array
bool inq[MAXN];
double d[MAXN];/*spfa*/
int p[MAXN]/*spfa*/,a[MAXN]/*????*/;
queue<int>q;
void Init_MCMF(){memset(first,-1,sizeof(first));en=0;}
void AddEdge(const int &U,const int &V,const int &W,const double &C)
{
u[en]=U; v[en]=V; cap[en]=W; cost[en]=C;
__next[en]=first[U]; first[U]=en++;
u[en]=V; v[en]=U; cap[en]=0; cost[en]=-C;
__next[en]=first[V]; first[V]=en++;
}
bool Spfa(int &Flow,double &Cost)
{
memset(d,0x7f,sizeof(d));
memset(inq,0,sizeof(inq));
d[S]=0; inq[S]=1; p[S]=0; a[S]=INF; q.push(S);
while(!q.empty())
{
int U=q.front(); q.pop(); inq[U]=0;
for(int i=first[U];i!=-1;i=__next[i])
if(cap[i] && d[v[i]]-(d[U]+cost[i])>EPS)
{
d[v[i]]=d[U]+cost[i];
p[v[i]]=i;
a[v[i]]=min(a[U],cap[i]);
if(!inq[v[i]]) {q.push(v[i]); inq[v[i]]=1;}
}
}
if(d[T]-2000000000.0>EPS) return 0;
Flow+=a[T]; Cost+=d[T]*(double)a[T]; int U=T;
while(U!=S)
{
cap[p[U]]-=a[T]; cap[p[U]^1]+=a[T];
U=u[p[U]];
}
return 1;
}
double Mincost()
{
int Flow=0;
double Cost=0;
while(Spfa(Flow,Cost));
return Cost;
}
int Zu,n,m;
int main(){
// freopen("g.in","r",stdin);
int x,y,z;
double p;
scanf("%d",&Zu);
for(int zu=1;zu<=Zu;++zu){
Init_MCMF();
scanf("%d%d",&n,&m);
S=n+1; T=n+2;
for(int i=1;i<=n;++i){
scanf("%d%d",&x,&y);
AddEdge(S,i,x,0);
AddEdge(i,T,y,0);
}
for(int i=1;i<=m;++i){
scanf("%d%d%d%lf",&x,&y,&z,&p);
if(z>0){
AddEdge(x,y,1,0);
AddEdge(x,y,z-1,-log(1.0-p));
}
}
printf("%.2lf
",1.0-pow(E,-Mincost()));
}
return 0;
}