Trò chơi khối hộp

Xem PDF

Điểm: 2200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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 × b × c\) đơn vị trên lưới hình chữ nhật \(H\) được chia thành \(m × 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 × 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)\). 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 ô.

Ví dụ, các hình vẽ trong Hình 2 dưới đây mô tả vị trí của khối hộp kích thước \(1 × 2 × 1\) sau khi thực hiện từng loại thao tác.

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.

Input

  • 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 độ của một ô đã bật sáng màu đỏ \((s = 1, 2, ..., k)\).

Output

  • Ghi 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.

Scoring

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

Example

Test 1

Input
1 2 1 3 3 2
2 2
3 3
Output
7
Note

Hình vẽ bên phải mô tả trạng thái bắt đầu trò chơi, trong đó hai ô tô đen là các ô sáng màu đỏ. Người chơi có thể thực hiện dãy thao tác: Lật sang phải, đẩy xuống dưới, đẩy lên trên, đẩy sang trái, đẩy sang trái, đẩy xuống dưới, đẩy xuống dưới, cuối cùng đẩy sang phải để bật được 7 ô của lưới sáng màu xanh.


Bình luận

Không có bình luận nào.