Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VOLAND - Chia đất

Sau khi thương lượng, cuối cùng Phú Ông quyết định sẽ cắt cho Bờm 2 khu đất trong quỹ đất của mình để đổi lấy chiếc quạt mo. Quỹ đất của phú ông có dạng R hàng ngang và C cột dọt gồm C thửa. Mỗi thửa có một giá trị kinh tế khác nhau (có thể âm).

Phú Ông đồng ý chia cho Bờm 2 khu đất, một khu hình chữ nhật kích thước B gồm A hàng ngang và B cột thửa đất nhỏ (lưu ý A * B khác B * A); và 1 khu đất “hình thoi” kích thước K sao cho:

  • Hai khu đất Bờm chọn không chứa thửa đất nào chung (không giao nhau).
  • Hai khu đất Bờm chọn phải nằm hoàn toàn trong khu đất của Phú Ông.

Biết rằng khu đất hình thoi với tâm ở thửa (x, y) và có kích thước K sẽ là tập hợp các thửa (x', y') thoả mãn |x’ - x| + |y’ - y| ≤ K. Phú ông cho Bờm lựa chọn tuỳ ý, Bờm cũng bắt đầu giao động trước đề nghị này. Bạn hãy giúp Bờm xác định 2 khu đất thoả mãn sẽ có giá trị kinh tế lớn nhất là bao nhiêu.

Input

Dòng đầu tiên ghi 5 số R, C, A, B, K.

Tiếp theo là R dòng, mỗi dòng ghi C số nguyên thể hiện giá trị kinh tế của các thửa đất.

Output

In ra giá trị kinh tế lớn nhất của 2 khu đất mà Bờm có thể chọn. Nếu không có cách chọn 2 khu đất thoả mãn, in ra "no solution".

Giới hạn

Trong tất cả các test, giá trị kinh tế của các thửa đất có trị tuyệt đối không vượt quá 106.

Subtask 1 (30% số điểm): R, C ≤ 50

Subtask 2 (40% số điểm): R, C ≤ 200

Subtask 3 (30% số điểm): R, C ≤ 1000

Ví dụ

Input 1:
5 5 2 2 1
1 1 1 1 1
1 2 2 2 1
1 2 2 2 1
1 2 2 2 1
1 1 1 1 1
Output 1:
16
Input 2:
5 5 2 2 3
1 1 1 1 1
1 2 2 2 1
1 2 2 2 1
1 2 2 2 1
1 1 1 1 1
Output 2:
no solution

Giải thích

Ở bộ test đầu tiên Bờm sẽ hời nhất nếu chọn 2 khu đất như sau:

1 1 1 1 1

1 2 2 2 1

1 2 2 2 1

1 2 2 2 1

1 1 1 1 1

Ở bộ test thứ hai Bờm không thể chọn khu đất "hình thoi" kích thước là 3 nào nằm hoàn toàn ở trong khu đất của Phú Ông.


Được gửi lên bởi:VOJ Team
Ngày:2015-12-25
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C C++ 4.3.2 PAS-GPC PAS-FPC
Nguồn bài:VNOI Online 2016

hide comments
2016-12-12 13:53:01
bài 2 hcn chưa đủ phải 1 hcn và 1 hình thoi, best
2015-12-28 18:14:56 Lollipop
best MEM :))
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.