Thành phố được mô tả bằng lưới N × MN × M (1 ≤ N, M ≤ 5001 ≤ N, M ≤ 500) với:

Cảnh sát:

KK cảnh sát xuất phát từ các ô riêng biệt.

Kẻ trộm:

TT kẻ trộm xuất phát từ các ô riêng biệt.

Chướng ngại vật động:

Một số ô bị chặn theo từng lượt di chuyển (ví dụ: ô (i,j)(i,j) chỉ chặn ở lượt chẵn).

Luật di chuyển:

Cảnh sát:

Di chuyển sang phải, xuống, hoặc đứng yên.

Kẻ trộm:

Di chuyển sang trái, lên, hoặc đứng yên.

Chướng ngại vật:

Thay đổi trạng thái theo hàm f(t) = (t mod 2).

Mục tiêu:

Tìm số lượt tối thiểu để ít nhất một cảnh sát bắt được ít nhất một kẻ trộm, đồng thời tối đa hóa số kẻ trộm bị bắt.

Input:

Dòng 1: N,M,K,TN,M,K,T.
KK dòng tiếp theo: Tọa độ (xi,yi)(xi,yi) của cảnh sát.
TT dòng tiếp theo: Tọa độ (xj,yj)(xj,yj) của kẻ trộm.
NN dòng cuối: Ma trận mô tả chướng ngại vật (00: tự do, 11: chặn ở lượt chẵn, 22: chặn ở lượt lẻ).

Output

Dòng 1: Số lượt tối thiểu để bắt đầu tiên.
Dòng 2: Số kẻ trộm tối đa có thể bắt được.