XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: caju.x, onde x deve ser c, cpp, java, js ou py

Colheita de Caju

Conrado é gerente em uma das fazendas de plantação de caju da Sociedade de Beneficiamento de Caju (SBC), um grupo que cultiva caju em grandes propriedades para o mercado externo.

Os cajueiros são plantados dispostos em linhas e colunas, formando uma espécie de grade. Na fazenda administrada por Conrado existem L linhas de cajueiros, cada uma formada por C colunas. Nesta semana Conrado deve executar a colheita da produção de um subconjunto contínuo de cajueiros. Esse subconjunto é formado por M linhas e N colunas de cajueiros. Há uma semana seus funcionários analisaram cada cajueiro da fazenda e estimaram a sua produtividade em número de cajus prontos para a colheita. Conrado agora precisa de sua ajuda para determinar qual a produtividade máxima estimada (em número de cajus) de uma área de M x N cajueiros.

Sua tarefa ó escrever um programa que, dado um mapa da fazenda contendo o número de cajus prontos para colheita em cada cajueiro, encontre qual o número máximo de cajus que podem ser colhidos na fazenda em uma área de M x N cajueiros.

Entrada

A primeira linha da entrada contém quatro números inteiros, L, C, M e N. L e C representam, respectivamente, o número de linhas e de colunas de cajueiros existentes na fazenda. M e N representam, respectivamente, o número de linhas e de colunas de cajueiros a serem colhidos. Cada uma das L linhas seguintes contém um inteiros, representando número de cajus prontos para colheita no cajueiro localizado naquela linha e coluna.

Saída

Seu programa deve imprimir uma única linha, contendo um único inteiro, o número máximo estimado de cajus que podem ser colhidos em uma área contínua de M x N. Esse número não será superior a 1 000 000.

Restrições

  • 1 ≤ L ≤ 1000
  • 1 ≤ C ≤ 1000
  • 1 ≤ M ≤ L
  • 1 ≤ N ≤ C

Exemplos

Entrada
3 3 1 1
1 2 3
1 3 3
1 10 1
Saída
10
Entrada
4 4 2 1
1 2 3 4
5 6 7 8
1 10 5 2
1 5 9 10
Saída
16
Entrada
5 5 2 2
1 1 1 3 1
1 2 1 1 1
1 1 1 2 1
1 1 2 1 1
1 3 1 1 3
Saída
7
 
Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação