1 /**************************************************************  2     Problem: 1834  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:64 ms  7     Memory:1296 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13   14 using namespace std; 15 const int N = 1005; 16 const int M = 10005; 17 const int inf = (int) 1e9; 18   19 struct Edges { 20     int x, y, c, w; 21 } E[M]; 22   23 struct edges { 24     int next, to, f, cost; 25     edges() {} 26     edges(int _n, int _t, int _f, int _c) : next(_n), to(_t), f(_f), cost(_c) {} 27 } e[M << 1]; 28   29 int n, m, k, last_ans; 30 int S, T; 31 int first[N], tot; 32 int q[N], d[N], g[N]; 33 bool v[N]; 34   35 inline int read() { 36     int x = 0, sgn = 1; 37     char ch = getchar(); 38     while (ch < ‘0‘ || ‘9‘ < ch) { 39         if (ch == ‘-‘) sgn = -1; 40         ch = getchar(); 41     } 42     while (‘0‘ <= ch && ch <= ‘9‘) { 43         x = x * 10 + ch - ‘0‘; 44         ch = getchar(); 45     } 46     return sgn * x; 47 } 48   49 inline void Add_Edges(int x, int y, int f, int c) { 50     e[++tot] = edges(first[x], y, f, c), first[x] = tot; 51     e[++tot] = edges(first[y], x, 0, -c), first[y] = tot; 52 } 53   54 bool bfs() { 55     memset(d, 0, sizeof(d)); 56     q[1] = S, d[S] = 1; 57     int l, r, x, y; 58     for (l = r = 1; l != (r + 1) % N; (++l) %= N) 59         for (x = first[q[l]]; x; x = e[x].next){ 60             y = e[x].to; 61             if (!d[y] && e[x].f) 62                 q[(++r) %= N] = y, d[y] = d[q[l]] + 1; 63         } 64   65     return d[T]; 66 } 67     68 int dinic(int p, int limit) { 69     if (p == T || !limit) return limit; 70     int x, y, tmp, rest = limit; 71     for (x = first[p]; x; x = e[x].next) 72         if (d[y = e[x].to] == d[p] + 1 && e[x].f && rest) {  73             tmp = dinic(y, min(rest, e[x].f)); 74             rest -= tmp; 75             e[x].f -= tmp, e[x ^ 1].f += tmp; 76             if (!rest) return limit; 77         } 78     if (limit == rest) d[p] = 0; 79     return limit - rest; 80 } 81     82 int Dinic() { 83     int res = 0, x; 84     while (bfs()) 85         res += dinic(S, inf); 86     return res; 87 } 88   89 void work1() { 90     int i; 91     memset(first, 0, sizeof(first)); 92     for (i = tot = 1; i <= m; ++i) 93         Add_Edges(E[i].x, E[i].y, E[i].c, 0); 94     S = 1, T = n; 95     printf("%d ", last_ans = Dinic()); 96 } 97   98 inline int calc() { 99     int flow = inf, x;100     for (x = g[T]; x; x = g[e[x ^ 1].to])101         flow = min(flow, e[x].f);102     for (x = g[T]; x; x = g[e[x ^ 1].to])103         e[x].f -= flow, e[x ^ 1].f += flow;104     return flow;105 }106   107 bool spfa() {108     int x, y, l, r;109     for (x = 1; x <= T; ++x)110         d[x] = inf;111     d[S] = 0, v[S] = 1, q[0] = S;112     for(l = r = 0; l != (r + 1) % N; ++l %= N) {113         for (x = first[q[l]]; x; x = e[x].next)114             if (d[q[l]] + e[x].cost < d[y = e[x].to] && e[x].f) {115                 d[y] = d[q[l]] + e[x].cost;116                 g[y] = x;117                 if (!v[y])118                     q[(++r) %= N] = y, v[y] = 1;119             }120         v[q[l]] = 0;121     }122     return d[T] != inf;123 }124  125 inline int work() {126     int res = 0;127     while (spfa())128         res += calc() * d[T];129     return res;130 }131  132 void work2() {133     int i;134     memset(first, 0, sizeof(first));135     for (i = tot = 1; i <= m; ++i) {136         Add_Edges(E[i].x, E[i].y, E[i].c, 0);137         Add_Edges(E[i].x, E[i].y, inf, E[i].w);138     }139     Add_Edges(n, n + 1, last_ans + k, 0);140     S = 1, T = n + 1;141     printf("%d\n", work());142 }143  144 int main() {145     int i;146     n = read(), m = read(), k = read();147     for (i = 1; i <= m; ++i)148         E[i].x = read(), E[i].y = read(), E[i].c = read(), E[i].w = read();149     work1();150     work2();151     return 0;152 }