Moving the Hay

内存限制：64 MiB 时间限制：5 Sec

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

样例输出

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

#1447. Moving the Hay

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示