Description
After he partitioned his farm into R (1 <= R <= 200) rows and C (1 <= C <= 200) squares conveniently labeled 1,1 through R,C, Farmer John spent days cutting the hay and stacking a huge amount of it in square 1,1. He then undertook the task of mapping out the N (1 <= N <= 80,000) haypaths through the farm so that he could deduce the maximum rate he could move hay from square 1,1 to square R,C. Each haypath uniquely connects the middle of two rectilinearly adjacent partitioned squares and has some capacity limit L_i (1 <= L_i <= 20,000,000) that is the maximum amount of hay that can be transported in either direction across the haypath. He's just positive that he can move hay at a reasonable rate to the other side of the farm but he doesn't know what the fastest rate is. Help him learn it.Input
* Line 1: Three separated integers: R, C, and N * Lines 2..N+1: Line i+1 describes path i with five space-separated integers: r1, c1, r2, c2, and L_i which denote a haypath connecting (r1,c1) to (r2,c2) with capacity L_i.Output
* Line 1: One number, on a line by itself, the maximum amount of material which can be transported from (1,1) to (R,C) simultaneously.Sample Input
3 3 8
1 1 1 2 5
1 1 2 1 3
1 2 2 2 5
2 1 2 2 2
2 2 2 3 1
2 2 3 2 6
2 3 3 3 4
3 2 3 3 7
INPUT DETAILS:
The grid is as follows:
*--5--* . . *
| |
3 5 :
| |
*--2--*--1--*
| |
: 6 4
| |
* . . *--7--*
Sample Output
7Hint
Consider the two edges coming out of (2,2), at most 6+1=7 units of hay can
be transported. This is indeed feasible.
