#1447. Moving the Hay

题目描述

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.

输入格式

• 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.

输出格式

• 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.

样例

样例输入

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--*  

样例输出

7  

数据范围与提示

Consider the two edges coming out of (2,2), at most 6+1=7 units of hay can
be transported. This is indeed feasible.