#include<cstdio>
#include<iostream>
#include<cstring>
#define M 100000
#define inf 2139062143
using namespace std;
struct data
{
int l,r,w;
}a[M];
int q[M],d[M],head[M],next[*M],u[*M],v[*M],cnt=,n,m,K,ans;
int cnt1=,head1[M],next1[*M],fro[*M],u1[*M],v1[*M],w1[*M],f[M],fr[M];
void jia(int a1,int a2,int a3)
{
cnt++;
u[cnt]=a2;
v[cnt]=a3;
next[cnt]=head[a1];
head[a1]=cnt;
}
void jia1(int a1,int a2,int a3,int a4)
{
cnt1++;
fro[cnt1]=a1;
u1[cnt1]=a2;
v1[cnt1]=a3;
w1[cnt1]=a4;
next1[cnt1]=head1[a1];
head1[a1]=cnt1;
}
bool bfs()
{
memset(d,,sizeof(int)*(*n));
int h=,t=;
q[]=;
d[]=;
for(;h<t;)
{
h++;
int p=q[h];
for(int i=head[p];i;i=next[i])
if(!d[u[i]]&&v[i])
{
d[u[i]]=d[p]+;
if(d[n])
return ;
t++;
q[t]=u[i];
}
}
return ;
}
int dinic(int s,int f)
{
if(s==n)
return f;
int rest=f;
for(int i=head[s];i&&rest;i=next[i])
if(v[i]&&d[u[i]]==d[s]+)
{
int now=dinic(u[i],min(rest,v[i]));
if(!now)
d[u[i]]=;
v[i]-=now;
v[i^]+=now;
rest-=now;
}
return f-rest;
}
bool spfa()
{
memset(d,,sizeof(int)*(*n));
d[]=;
f[]=;
q[]=;
int h=,t=;
for(;h<t;)
{
h++;
int p=q[h];
f[p]=;
for(int i=head1[p];i;i=next1[i])
if(v1[i]&&d[u1[i]]>d[p]+w1[i])
{
d[u1[i]]=d[p]+w1[i];
fr[u1[i]]=i;
if(!f[u1[i]])
{
f[u1[i]]=;
t++;
q[t]=u1[i];
}
}
}
if(d[n]!=inf)
return ;
return ;
}
void mcf()
{
int mx=inf;
for(int i=fr[n];i;i=fr[fro[i]])
mx=min(mx,v1[i]);
for(int i=fr[n];i;i=fr[fro[i]])
{
v1[i]-=mx;
v1[i^]+=mx;
ans+=mx*(w1[i]);
}
}
int main()
{
scanf("%d%d%d",&n,&m,&K);
for(int i=;i<=m;i++)
{
int a3;
scanf("%d%d%d%d",&a[i].l,&a[i].r,&a3,&a[i].w);
jia(a[i].l,a[i].r,a3);
jia(a[i].r,a[i].l,);
}
for(;bfs();)
ans+=dinic(,inf);
printf("%d ",ans);
for(int i=;i<=cnt;i+=)
{
jia1(a[i/].l,a[i/].r,inf,a[i/].w);
jia1(a[i/].r,a[i/].l,,-a[i/].w);
jia1(a[i/].l,a[i/].r,v[i],);
jia1(a[i/].r,a[i/].l,v[i+],);
}
jia1(,,K,);
jia1(,,,);
ans=;
for(;spfa();)
mcf();
printf("%d\n",ans);
return ;
}
一遍最大流，一遍费用流。第一问跑完之后在残余网络建边，单位费用为扩容费用，