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

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

Margaridas

Leopoldo ó gerente de uma plantação de flores da Associação de Cultivo de Margaridas (ACM), um grupo que cultiva margaridas em grandes propriedades para abastecer floriculturas em grandes cidades.

As margaridas são plantadas em vasos dispostos em linhas e colunas, formando uma espécie de grade. Na plantação administrada por Leopoldo existem L linhas de vasos de margaridas, cada uma formada por C vasos. Para facilitar o gerenciamento, os vasos são organizados em lotes de M linhas e N colunas de vasos, sendo que não existem sobreposições entre os lotes (não existe nenhuma linha ou coluna comum a mais de um lote) e todos os lotes têm exatamente M linhas e N colunas.

A colheita é sempre feita em um único lote, coletando-se todas as margaridas daquele lote que estejam prontas para a venda. Uma semana antes de fazer a colheita, os funcionários da plantação analisaram cada vaso e anotaram quantas margaridas estarão prontas para venda na semana seguinte. Leopoldo agora precisa da sua ajuda para determinar qual o número máximo de margaridas que poderá ser colhido em um único lote de M x N vasos.

Sua tarefa é escrever um programa que, dado um mapa da plantação contendo o número de margaridas prontas para venda em cada vaso, encontre qual o número máximo de margaridas que podem ser colhidos por Leopoldo.

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 vasos existentes na plantação. M e N representam respectivamente o número de linhas e de colunas dos lotes. As L linhas seguintes contêm inteiros cada, representando o número de margaridas prontas para colheita no vaso localizado naquela linha e coluna. Note que vasos que L/M e C/N são sempre inteiros, pois não há linha ou coluna de vasos que pertençam a mais de um lote.

Saída

Seu programa deve imprimir uma única linha contendo o número máximo de margaridas que podem ser colhidas em um lote de M x N. Esse número não é superior a 1 000 000.

Restrições

  • 1 ≤ L ≤ 1000
  • 1 ≤ C ≤ 1000
  • 1 ≤ M ≤ L
  • 1 ≤ N ≤ C
  • A resposta é menor do que 1 000 000.

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
15
Entrada
6 6 2 2
1 1 1 1 1 1
1 2 2 1 1 2
1 2 2 1 1 1
1 1 1 1 1 1
1 3 1 1 3 1
1 1 1 1 2 1
Saída
4
Tarefas Programação Nível 1
Promoção
logo sbc
Patrocínio
Apoio
Coordenação