CZ 追 QC

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

很久很久以前,有一个古老的传说,在遥远的地方有富可敌国的宝藏,CZ听说了这个故事,他下决心要找到藏宝图去寻宝藏,皇天不负有心人,历经18年,他终于找到了。不巧的是,被QC看到了,QC悄悄的拿去复印了一份。就这样两人都开始了寻宝之路,下面是藏宝图的平面图,红色代表障碍物,不可越过,黑色是CZ,紫色代表QC。

 


       CZ的左下指梅红色区域,右上指蓝色区域。

每个位置都有自己的等级,等级的大小等于此位置左下的障碍物(包括QC和CZ)的数量之和。CZ的藏宝图只显示自己的位置和障碍物的位置,只有最高的等级才可以得到宝藏,急脾气的CZ想知道自己的等级排名,你能帮他算出他在所有障碍物和QC中的等级排名(由大到小)吗?(如图所示:CZ等级为2,QC等级为7,各个障碍物的等级分别为0,1,1,3,3,6。所以CZ的名次为4,等级相同时,CZ名次最高),

真藏宝图具有防伪功能,当QC位于CZ的右上方时,QC会被施予魔法,呆在原地不能移动,只有当CZ位于QC的右上时,QC的魔法才能解除,假设CZ移动一格需要一天的时间,请算出QC魔法被解除的时间(以天为单位)。(如图所示:时间为5天,图中红色路线。)

Input

第一行是输入两个数w,h分别代表藏宝图的宽和长,(0<=w,h<=2000)。第二行包含一个数N(0

规定:

x,y左下的点:xi<=x&&yi<=y。

x,y右上的点:  xi>=x&&y>=yi。

Output

输出CZ的等级排名,和他要超过QC的时间天数,若超不过输出-1。

Sample Input

6 6
6
1 2
5 5
4 5
2 3
5 3
5 2
3 4
5 6

Sample Output

5 5

Hint

 

Source

shangcanfang