Giải bài trực tuyến

Hình thức kiểm tra IQ hiện nay mà người ta vẫn hay dùng đang cho thấy những khuyết điểm lớn. Đó là sự dập khuôn, không đa dạng. Một người chỉ sau vài lần làm thử các bài test IQ sẽ quen với các dạng đề bài như dãy quy luật, chọn hình sai v.v... Như vậy thì bài thi IQ sẽ không còn ý nghĩa kiểm tra độ thông minh, sáng tạo của con người nữa. Để khắc phục người ta vừa phát minh ra một hình thức kiểm tra chỉ số IQ mới. Đó là một trò chơi với một bảng gồm M dòng và N cột. Để thuận tiện, người ta đánh số các dòng từ 1 đến M theo chiều từ trên xuống, các cột từ 1 đến N theo chiều từ trái sang phải. Một ô của bảng sẽ được thể hiện bằng một cặp số nguyên (u, v) trong đó u là chỉ số dòng, v là chỉ số cột. Trong số M × N ô của bảng, sẽ có một số ô có chướng ngại vật. Ban đầu, tại một số ô, người ta để sẵn một số viên bi. Nhiệm vụ của bạn là đưa các viên bi đó về một số ô đích. Để làm được điều đó, bạn được sử dụng các phép quay bảng sang trái/phải (ngược chiều kim đồng hồ/thuận chiều kim đồng hồ). Các phép quay có thể được mô tả như sau:

Giải thích:

Hình 1 sau khi quay phải (thuận chiều kim đồng hồ) được hình 2.

Ở hình 2, do trọng lực, viên bi rơi xuống. Ta có bảng như hình 3.

Hình 3 sau khi quay trái (ngược chiều kim đồng hồ) được hình 4.

Ở hình 4, do trọng lực, viên bi rơi xuống. Ta có bảng như hình 5.

Yêu cầu:

Đề thi IQ không bao giờ đơn giản. Trong bảng M × N, sẽ không chỉ có một viên bi mà sẽ có K viên bi. Bạn sẽ phải đưa K viên bi này đến K ô đích bằng ít lần xoay bảng nhất. Cũng nói thêm rằng, trong quá trình xoay bảng và quá trình các viên bi rơi xuống, không có hai viên bi nào đồng thời ở một ô. Nếu hai viên bi cùng trên một cột rơi xuống, hai viên bi sẽ nằm ở hai ô liên tiếp, trên dưới nhau.

Input

Dòng đầu ghi ba số M, N và K.

K dòng tiếp theo, mỗi dòng ghi một cặp số là tọa độ của một ô đích.

M dòng tiếp theo, mỗi dòng ghi một xâu độ dài N thể hiện trạng thái ban đầu của bảng. Xâu gồm các kí tự “#” thể hiện ô chướng ngại vật, “.” thể hiện ô trống, “o” thể hiện một viên bi.

Dữ liệu vào đảm bảo tại thời điển ban đầu, các viên bi luôn được đặt phía trên một ô chướng ngại vật hoặc ở hàng dưới cùng của bảng. Dữ liệu vào cũng đảm bảo luôn có ít nhất một cách làm.

Output

Gồm 1 dòng duy nhất ghi P là số lần xoay bảng ít nhất

Example

Input:
5 5 1
5 4
#....
.o..#
.#...
.....
..#..

Output:
2

Giới hạn:
1 ≤ M, N ≤ 10 
1 ≤ K ≤ 4