Khu vườn hoa

View as PDF

Submit solution

Points: 0.77 (partial)
Time limit: 0.9s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
IOI
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Khải Hạnh trồng ~n~ cây hoa hồng trong khu vườn của mình -- khu vườn được coi là đẹp nhất ở Đồng Tháp với những bông hoa nở thật to và đẹp khi hè về. Khải Hạnh thấy rằng mình không thể vừa đi học vừa chăm sóc tất cả hoa hồng trong vườn, vì thế cậu đã quyết định thuê thêm hai người làm vườn. Khải Hạnh muốn chọn hai vùng hình chữ nhật trong vườn để phân cho hai người làm vườn chăm sóc hoa hồng trên đó. Các phần vườn này được tách rời nhau và trên mỗi phần có ~k~ cây hoa hồng.

Khải Hạnh muốn dựng hàng rào xung quanh các vùng chữ nhật đó, nhưng do không có nhiều tiền vì vậy cậu muốn dựng được hàng rào càng nhỏ càng tốt. Nhiệm vụ của bạn là giúp Khải Hạnh chọn hai vùng chữ nhật này để rào.

Khu vườn có dạng một hình chữ nhật với chiều dài ~L~ mét và chiều rộng ~W~ mét, được chia thành ~L \times W~ hình vuông với kích thước ~1~ mét ~\times~ 1 mét để trồng hoa hồng vào đó. Ta đưa vào một hệ tọa độ có các trục song song với các cạnh của khu vườn. Tất cả các hình vuông có các tọa độ nguyên ~(x~, ~y)~ thỏa mãn ~1 \leq x \leq L~, ~1 \leq y \leq W~. Thay vì mỗi ô vuông trồng một cây hoa hồng, Khải Hạnh muốn khu vườn của mình trong tự nhiên nên đã trồng không theo quy tắc nào cả :D. Do vậy trong khu vườn của cậu, mỗi hình vuông có thể không có cây hoa hồng nào hoặc chứa một số bất kỳ các cây hoa hồng.

Hình chữ nhật được chọn để rào có các cạnh song song với các cạnh của khu vườn, các hình vuông trong các góc của chúng đều có tọa độ nguyên. Cho ~1 \leq L_1 \leq L_2 \leq L~; ~1 \leq W_1 \leq W_2 \leq W~, vùng hình chữ nhật được chọn với các góc có tọa độ là ~(L_1, W_1)~, ~(L_1, W_2)~, ~(L_2, W_1)~, và ~(L_2, W_2)~ sẽ:

  • Chứa tất cả các hình vuông với tọa độ ~(x~, ~y)~ thỏa mãn ~L_1 \leq x \leq L_2~ và ~W_1 \leq y \leq W_2~ và
  • Có chu vi là ~2 \cdot (L_2 - L_1 + 1) + 2 \cdot (W_2 - W_1 + 1)~.

Hai vùng chữ nhật phải tách rời nhau, tức là chúng không chứa một hình vuông chung nào. Thậm chí nếu chúng có một cạnh chung hoặc một phần của nó, chúng cũng phải được bao xung quanh bởi các hàng rào riêng rẽ.

Hãy giúp Khải Hạnh tìm ra ~2~ hình chữ nhật tốt nhất thỏa yêu cầu sao cho chu vi là nhỏ nhất. Hoặc nếu không thể tìm được thì phải báo để Khải Hạnh biết đường mà lo liệu :D

Input

  • Dòng đầu tiên của input chuẩn chứa hai số nguyên: ~L~ và ~W~ ~(1 \leq L~, ~W \leq 250)~ cách nhau bởi một dấu trắng -- mô tả chiều dài và chiều rộng của khu vườn.
  • Dòng thứ hai chứa hai số nguyên: ~n~, ~k~ ~(2 \leq n \leq 5000~, ~1 \leq k \leq \frac{n}{2})~ cách nhau bởi một dấu trắng -- mô tả số các cây hoa trong vườn và số các cây hoa có trong mỗi miền chữ nhật được chọn.
  • ~n~ dòng tiếp theo chứa tọa độ của các cây hoa hồng, mỗi dòng chứa tọa độ của một cây. Dòng thứ ~(i + 2)~ chứa hai số nguyên ~L_i~, ~W_i~ ~(1 \leq L_i \leq L~, ~1 \leq W_i \leq W)~ cách nhau bởi một dấu trắng -- mô tả tọa độ của hình vuông chứa cây hoa hồng thứ ~i~. Hai hoặc nhiều hơn cây hoa hồng có thể được đặt trong cùng một ô vuông.

Output

Kết quả ghi ra trên một dòng với chỉ một số nguyên -- mô tả tổng nhỏ nhất các chu vi miền chữ nhật riêng rẽ này, mỗi miền có chứa chính xác ~k~ cây hoa hồng, hoặc ghi ra từ "NO", nếu không có cặp hình chữ nhật nào tồn tại.

Giới hạn

Trong ~50\%~ test, kích thước của khu vườn thỏa mãn ~L~, ~W \leq 40~.

Sample Input

6 5
7 3
3 4
3 3
6 1
1 1
5 5
5 5
3 1

Sample Output

22

Comments

Please read the guidelines before commenting.


There are no comments at the moment.