Moving the Hay

农场被划分为 $R$ 行、$C$ 列的方格，方格坐标从 $(1,1)$ 到 $(R,C)$。农夫约翰将收割的干草全部堆放在方格 $(1,1)$ 中，现在他希望通过农场中的 $N$ 条运输路径，将干草运送到方格 $(R,C)$。

每条运输路径连接两个上下或左右相邻方格的中心。第 $i$ 条路径的容量为 $L_i$，表示在任意一个方向上通过这条路径运输干草的最大速率。

请计算从方格 $(1,1)$ 到方格 $(R,C)$ 同时运输干草的最大速率。

输入格式

第一行包含三个以空格分隔的整数 $R$、$C$ 和 $N$。

接下来 $N$ 行，第 $i$ 行包含五个以空格分隔的整数 $r_1$、$c_1$、$r_2$、$c_2$ 和 $L_i$，表示有一条容量为 $L_i$ 的双向运输路径，连接方格 $(r_1,c_1)$ 与 $(r_2,c_2)$。

输出格式

输出一个整数，表示从方格 $(1,1)$ 到方格 $(R,C)$ 同时运输干草的最大速率。

样例输入

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

样例输出

7

样例解释

考虑从方格 $(2,2)$ 出发的两条路径，它们的容量之和至多为 $6+1=7$，因此运输速率不可能超过 $7$。同时，确实存在运输速率为 $7$ 的可行方案。

数据范围

• $1\le R\le 200$；
• $1\le C\le 200$；
• $1\le N\le 8\times 10^4$；
• $1\le L_i\le 2\times 10^7$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 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

输出

7