Giải bài trực tuyến

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 R * 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 A * 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á 10⁶.

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.