Một giá đựng đồ dựng đứng hình chữ nhật chia thành M×N ô gồm M hàng đánh số 1..M từ dưới lên và N cột đánh số 1..N từ trái sang phải. Mỗi khi cần lấy đồ đạc tại một ô (i,j) (hàng i, cột j) nào đó, người ta phải dùng một cái thang dựng đứng theo cột j để leo lên, trong quá trình leo, có thể lấy đồ đạc tại các ô trên cột j và hai cột kề bên cột j với điều kiện các ô đó không cao hơn ô tại vị trí leo lên tại cột j.

Ta cần lấy đồ vật tại một số ô, hãy chọn một số cột đặt thang sao cho hai yêu cầu sau được thoả mãn:

• Lấy được mọi đồ vật cần lấy:

• Tổng các chiều cao thang cần leo là nhỏ nhất (mỗi lần đặt thang tại một cột, chiều cao thang được tính bằng chỉ số ô cao nhất cần leo lên tại cột đó).

Dữ liệu:

• Dòng thứ nhất ghi hai số nguyên dương M<=10000, N<=1000;

• Dòng thứ hai ghi số nguyên dương K là số ô cần lấy đồ tại đó, K<=1000;

• Trong K dòng tiếp theo, mỗi dòng ghi hai số u,v có nghĩa là cần lấy đồ ở ô tại cột u dòng v.

Kết quả:

• Ghi ra một số duy nhất T là tổng chiều cao thang cần leo.

Dữ liệu:

10 10
5
9 1
7 6
5 8
4 1
3 2

Kết quả:

11