#101447. [BZOJ 1447] Moving the Hay

After he partitioned his farm into rows and squares conveniently labeled through , Farmer John spent days cutting the hay and stacking a huge amount of it in square . He then undertook the task of mapping out the haypaths through the farm so that he could deduce the maximum rate he could move hay from square to square . Each haypath uniquely connects the middle of two rectilinearly adjacent partitioned squares and has some capacity limit 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 : Three separated integers: , and

Lines : Line describes path with five space-separated integers: which denote a haypath connecting to with capacity .

Line : One number, on a line by itself, the maximum amount of material which can be transported from to simultaneously.

样例输入 #1

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

样例输出 #1

7

样例解释

The grid is as follows:

*--5--* . . *
|     |     
3     5     :
|     |    
*--2--*--1--*
      |     |
:     6     4
      |     |
* . . *--7--*

对于 的数据，，，。