1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #define N 102333 5 #include<queue> 6 #define inf 2147483647 7 using namespace std; 8 inline int read(){ 9      int x=0; char ch=getchar();10      while(ch<‘0‘||ch>‘9‘) ch=getchar();11      while(ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-48,ch=getchar();12      return x;13 }14 struct node{15      int w,to,next,c,from;16 }e[N<<1],E[N<<1];17 int head[N],dis[N],from[N],i,j,zs1,zs2,zs3,zs4,tot=1,t,anss,m,n,sum,flow;18 bool vis[N];19 int tot1,tot2,num[N][2];20 inline void ins(int u,int v,int w,int cost){21      e[++tot].to=v; e[tot].next=head[u]; head[u]=tot; e[tot].w=w; e[tot].c=cost; e[tot].from=u;22 }23 inline bool spfa(){24      for(int i=0;i<=t;i++) dis[i]=inf; vis[0]=1; dis[0]=0; queue<int>q; q.push(0);25      while(!q.empty()) {26           int x=q.front(); q.pop();27           for(int k=head[x];k;k=e[k].next)28             if (dis[x]+e[k].c<dis[e[k].to] && e[k].w>0) {29                     from[e[k].to]=k;30                 dis[e[k].to]=dis[x]+e[k].c;31                 if(!vis[e[k].to]) {32                      vis[e[k].to]=1; q.push(e[k].to);33                 }34             }35           vis[x]=0;36      }37      if(dis[t]==inf) return 0;else return 1;38 }39 inline bool bfs(){40      for(i=0;i<=t;i++) dis[i]=-1; queue<int>q; q.push(1); dis[1]=0;41      while(!q.empty()) {42           int x=q.front(); q.pop();43           for(int k=head[x];k;k=e[k].next) 44              if(dis[e[k].to]<0 && e[k].w>0) {45                    dis[e[k].to]=dis[x]+1; q.push(e[k].to);46              }47      }48      if(dis[t]>0) return 1;else return 0;49 }50 int find(int x,int low){51      if(x==t) return low;52      int delta=low,now;53      for(int k=head[x];k;k=e[k].next) 54        if(e[k].w>0 && dis[e[k].to]==dis[x]+1){ 55            now=find(e[k].to,min(e[k].w,delta));56            e[k].w-=now; e[k^1].w-=now;   delta-=now;57            if(!delta) return low;58         } 59      dis[x]=-1;60      return low-delta;61 }62 inline void run() {63      int x=inf;64      for(int i=from[t];i;i=from[e[i].from]) x=min(x,e[i].w);65      for(int i=from[t];i;i=from[e[i].from]) {66          anss+=e[i].c*x;e[i].w-=x; e[i^1].w+=x;67      }68 }69 int main () {70      n=read(); int road=read();m=read(); t=n;71      for(i=1;i<=road;i++) {72           zs1=read(),zs2=read(),zs3=read(),zs4=read();73           ins(zs1,zs2,zs3,0); ins(zs2,zs1,0,0); num[++tot1][0]=tot-1,num[tot1][1]=zs3;74           E[++tot2].from=zs1; E[tot2].to=zs2; E[tot2].c=zs4;75      }76      while(bfs()){77           while(sum=find(1,inf)) flow+=sum;78      }79      printf("%d ",flow);80      for(i=1;i<=tot1;i++) {81           e[num[i][0]].w=num[i][1]; e[num[i][0]^1].w=0;82      }83      int u,v,cost;84      ins(0,1,flow+m,0),ins(1,0,0,0);85      for(i=1;i<=tot2;i++) {86           u=E[i].from,v=E[i].to,cost=E[i].c;87           ins(u,v,inf,cost); ins(v,u,0,-cost);88      }89      while(spfa()) run(); 90      printf("%d",anss); 91 }