Problem D: 着火的房间II

Problem D: 着火的房间II

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 262  Solved: 93
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI被困在一个由nxm个方格组成的房间中了,PIPI最开始的位置在(1,1),安全出口位置在 (n,m)。房间中有些方格是永远安全的,而有一些方格在某一段时间会喷火,如果PIPI在到达某一个方格之后方格刚好在喷火,那么PIPI就GG了。如果PIPI到达了安全出口,那么PIPI就安全闯过了火海。
每一个单位时间,PIPI都必须向上下左右四个方向相邻方格移动一格。
现在PIPI知道了如下信息:
1. (1,1)和(n,m)处的方格永远是安全的。
2. 每一个方格喷火时间连续,并且PIPI知道哪段时间会喷火(每个方格只会喷火一次)。
现在PIPI想尽快的离开这个房间,请你告诉PIPI最快几个单位时间能够顺利离开房间。

Input

第一行包含三个整数n,m,q,表示小屋中方格的的行、列,以及喷火的方格数(1<=n,m<=100, t<=n*m-2)。
接下来q行,每行4个整数a,b,c,d,表示第a行第b列的方格在[c,d]时刻会喷火 (1<=a<=b<=100, 0=<c<=d<=100)。

Output

输出一行,表示PIPI可以最快离开房间的时间,如果PIPI不能离开房间,输出-1。

Sample Input

3 3 3
2 1 1 1
1 3 2 10
2 2 2 10

Sample Output

6