Challenge of Wisdom

Time Limit: Java: 2000 ms / Others: 2000 ms

Memory Limit: Java: 32768 KB / Others: 32768 KB

Description

Background

"Then, I want to know whether you're a wise boy!"

Problem

"I have a great deal of lands. They're divided into N*M grids (N, M <= 1,000,000,000). When you are in (x, y), you may move into (x+1, y) or (x, y+1). I have P (P <= 100,000) treasures in the lands; each time, you can pick up anything you like."

"Now, I'll give you a map of my treasures; tell me, wise boy, how many times you need to pick up all the treasures?"

Input

This problem contains multiple test cases.

Each test case begins with 3 integers N, M and P. then followed by P lines, each lines contains 2 numbers: x, y, representing the location of a treasure.

Output

For each test case, output the minimum times I need.

Sample Input

		7 7 7
		1 2
		1 4
		2 4
		2 6
		4 4
		4 7
		6 6

Sample Output

		2

  Contest: A Great Beloved and My Gate to Freedom
	  There is a cx, there is a love_cx.

Hint

None

Source

JIANG, Yanyan's Contest #2

提交代码