Công việc của Ivana là chuyển bánh pizza. Hàng ngày, anh ta nhận được 1 danh sách các địa điểm nhận bánh.

Thành phố được mô tả là bản đồ ~R*C~ ô, ~(1, 1)~ cho đến ~(R, C)~. Cho phép di chuyển từ 1 ô sang trái hoặc phải. Chỉ được phép đi lên/xuống ở cột ~1~ hoặc ~C~.

Ivana xuất phát từ ~(1,1)~ và mang theo mọi bánh pizza cần chuyển. Tại mỗi ô, Ivana biết thời gian mà anh ta cần để đi qua ô đó. Tính thời gian nhỏ nhất để cung cấp tất cả các pizza. Biết rằng bánh pizza phải được cung cấp theo đúng thứ tự xuất hiện trong danh sách yêu cầu

Input

Dòng đầu là hai số ~R,C~ (~1 \le R \le 2000~, ~1 \le C \le 200~), ~R~ dòng tiếp theo, mỗi dòng ~C~ số nguyên ~\ge 0~ và ~\le 5000~.

Dòng sau đó chứa ~D~ ~(1 \le D \le 200000)~, số pizza cần chuyển. ~D~ dòng tiếp theo, mỗi dòng hai số ~A, B~ ~(1 \le A \le R, 1 \le B \le C)~, vị trí nhận bánh.

Mỗi vị trí xuất hiện ~\le 1~ lần.

Output

Thời gian cung cấp pizza nhỏ nhất.

Sample Input 1

3 3
1 8 2
2 3 2
1 0 1
3
1 3
3 3
2 2

Sample Output 1

17

Sample Input 2

2 5
0 0 0 0 0
1 4 2 3 2
4
1 5
2 2
2 5
2 1

Sample Output 2

9

Note

Ở ví dụ 1, cách đi nhanh nhất là : ~(1, 1), (2, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3), (2, 3), (3, 3), (2, 3)~ và ~(2, 2)~. và thời gian tương ứng là ~1+2+1+0+1+2+2+2+1+2+3=17~