Trò chơi khối hộp

Trò chơi khối hộp là một trò chơi với một khối hộp chữ nhật kích thước $a\times b\times c$ đơn vị trên lưới hình chữ nhật $H$ được chia thành $m\times n$ ô vuông đơn vị. Các hàng của lưới được đánh số từ $1$ tới $m$ từ trên xuống dưới và các cột của lưới được đánh số từ $1$ tới $n$ từ trái qua phải. Ô nằm trên giao của hàng $i$ và cột $j$ được gọi là ô $(i,j)$. Ban đầu, khối hộp được đặt ở góc trái trên của lưới $H$, cụ thể mặt đáy khối hộp chiếm đúng $a\times b$ ô của lưới, là các ô nằm trong hình chữ nhật con của lưới $H$ với ô ở góc trái trên là $(1,1)$ và ô ở góc phải dưới là $(a,b)$ (khối hộp cao $c$). Mỗi bước, người chơi có thể thực hiện một trong các loại thao tác sau:

• Đẩy khối hộp tịnh tiến lên trên, xuống dưới, sang trái hoặc sang phải một ô;
• Lật khối hộp lên trên, xuống dưới, sang trái hoặc sang phải một ô.

Khi lật, khối hộp quay $90$ độ quanh cạnh đáy ở phía được lật. Chẳng hạn, nếu mặt đáy đang chiếm $p$ hàng, $q$ cột và khối hộp cao $h$ thì sau khi lật sang phải, mặt đáy chiếm cùng $p$ hàng đó và $h$ cột nằm ngay bên phải các cột cũ, còn khối hộp cao $q$; lật sang trái tương tự với $h$ cột nằm ngay bên trái. Sau khi lật lên trên, mặt đáy chiếm cùng $q$ cột đó và $h$ hàng nằm ngay phía trên các hàng cũ, còn khối hộp cao $p$; lật xuống dưới tương tự với $h$ hàng nằm ngay phía dưới. Ví dụ, với khối hộp kích thước $1\times 2\times 1$ nằm ở hàng $2$, cột $2$ và $3$ của một lưới $3\times 4$: đẩy sang phải đưa nó tới cột $3$ và $4$; lật sang phải đưa nó thành khối đứng chiếm đúng ô $(2,4)$ (cao $2$); lật sang trái đưa nó thành khối đứng chiếm đúng ô $(2,1)$; lật lên trên đưa nó tới hàng $1$, cột $2$ và $3$ (cao $1$).

Khi bắt đầu chơi, tất cả các ô mà khối hộp đè lên được bật sáng màu xanh và có $k$ ô khác trên lưới được bật sáng màu đỏ, các ô còn lại ở trạng thái tắt. Một thao tác được gọi là hợp lệ, nếu sau khi thực hiện thao tác này, khối hộp vẫn nằm gọn trên lưới $H$ và không đè lên ô sáng màu đỏ nào. Sau khi một thao tác được thực hiện, những ô bị khối hộp đè lên đang ở trạng thái tắt sẽ được bật sáng màu xanh, những ô đang sáng xanh vẫn giữ nguyên trạng thái bật sáng màu xanh. Nhiệm vụ của người chơi là tìm cách thực hiện dãy các thao tác hợp lệ để bật được nhiều ô sáng màu xanh nhất.

Yêu cầu: Cho kích thước khối hộp, kích thước của lưới $H$ và vị trí của các ô sáng màu đỏ, hãy xác định số lượng nhiều nhất các ô được bật sáng màu xanh mà người chơi có thể đạt được.

Dữ liệu vào

• Dòng thứ nhất chứa sáu số nguyên dương $a$, $b$, $c$, $m$, $n$, $k$, các số được ghi cách nhau bởi dấu cách;
• Dòng thứ $s$ trong số $k$ dòng tiếp theo chứa hai số nguyên dương được ghi cách nhau bởi dấu cách $x_s,y_s$ là tọa độ (hàng, cột) của một ô đã bật sáng màu đỏ $(s=1,2,\dots ,k)$.

Dữ liệu ra

In ra một số nguyên duy nhất là số lượng nhiều nhất các ô được bật sáng màu xanh mà người chơi có thể đạt được.

Ràng buộc

• $m,n\le 1000$;
• $a\le m$, $b\le n$; các ô đỏ khác nhau và không nằm dưới khối hộp lúc ban đầu.

Subtasks

• Subtask 1 ($25\%$ số test, $25\%$ số điểm): $a=b=c=1$; $m,n\le 100$;
• Subtask 2 ($25\%$ số test, $25\%$ số điểm): $a=b=c$; $m,n\le 100$;
• Subtask 3 ($25\%$ số test, $25\%$ số điểm): $m,n\le 100$;
• Subtask 4 ($25\%$ số test, $25\%$ số điểm): $m,n\le 1000$.

Ví dụ