Por OBI - Olimpíada Brasileira de Informática 2006 Brazil
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 da sua ajuda para determinar qual a produtividade máxima estimada (em número de cajus) de uma área de M × 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 × N cajueiros.
A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). 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 (1 ≤ L ≤ 1000) e de colunas (1 ≤ C ≤ 1000) de cajueiros existentes na fazenda. M e N representam, respectivamente, o número de linhas (1 ≤ M ≤ L) e de colunas (1 ≤ N ≤ C) de cajueiros a serem colhidos. As L linhas seguintes contêm C inteiros cada, representando número de cajus prontos para colheita no cajueiro localizado naquela linha e coluna.
Seu programa deve imprimir, na saída padrão, uma única linha que contém o número máximo estimado de cajus que podem ser colhidos em uma área contínua de M × N. Esse número não será superior a 1000000.
Exemplos de Entrada | Exemplos de Saída |
3 3 1 1 1 2 3 1 3 3 1 10 1 |
10 |
4 4 2 1 1 2 3 4 5 6 7 8 1 10 5 2 1 5 9 10 |
16 |
5 5 2 2 |
7 |