Problema C - Vigiando a Fronteira

A companhia de desenvolvimento de jogos OGPro (Olympiad Game Programmers) está a desenvolver um novo jogo de estratégia em tempo real com tecnologia de inteligência artificial do mais recente que existe. O jogo envolve estratégia militar e muitos pequenos subproblemas precisam de ser resolvidos. Tu fazes parte da equipa de desenvolvimento e estás encarregado de distribuir automaticamente as torres de vigia que irão controlar uma importante linha fronteiriça.

A fronteira pode ser pensada como uma linha recta. Todas as torres de vigia têm um igual alcance pré-determinado que é igual a um número inteiro de quilómetros. Certos pontos da fronteira (os chamados pontos críticos) são mais importantes e por isso mesmo têm de ser mais fortemente vigiados. Estes pontos são indicados por uma única coordenada, indicando a distância em quilómetros do início da fronteira. A figura seguinte exemplifica uma fronteira com 6 pontos críticos a 1, 2, 3, 5, 8 e 10 quilómetros.

.

O objectivo é colocar as torres de vigia de modo a maximizar o número de pontos críticos vigiados. Por exemplo, se as torres de vigia tiveram um alcance de 1 quilómetro (significa que controlam todos os pontos a distância menor ou igual a 1quilómetro da sua localização), e se apenas tiveres uma torre para colocar, esta deveria ficar na posição 2quilómetro, controlando assim 3 pontos críticos, como podes ver na figura seguinte:

.

Se, nas mesmas circunstâncias, pudesses colocar 2 torres de vigia, já seria possível controlar 5 pontos críticos, como se pode ver na figura a seguir:

.

Se fosse possível colocar 3 torres, então todos os 6 pontos críticos podiam ser controlados. Entre várias hipóteses de colocação das torres, esta assegurava esse mesmo controlo:

.

O Problema

Escreve um programa que dadas as localizações dos pontos críticos na fronteira, o número de torres de vigia disponíveis e o respectivo alcance, calcula o número máximo de pontos críticos que é possível vigiar, colocando as torres em posições de coordenadas inteiras, diferentes entre si (não é possível colocar duas torres no mesmo sítio), ao longo da fronteira.

Input

Na primeira linha de input vêm dois números inteiros positivos, T e A, separados por um único espaço. T indica o número de torres de vigia e A o alcance em quilómetros (1 ≤ T ≤ 100, 0 ≤ A ≤ 50).

Na segunda linha vem um único número inteiro positivo P indicando o número de pontos críticos (1 ≤ P ≤ 1 000 e T ≤ P). Seguem-se exactamente P linhas, cada uma contendo um número inteiro positivo indicando a localização Pi de um ponto crítico em quilómetros (0 ≤ Pi ≤ 5 000). Os pontos críticos podem vir em qualquer ordem no input. É garantido que todos os pontos críticos estão em locais diferentes uns dos outros.

Output

O output é constituído por uma única linha, a qual contém o número máximo de pontos críticos que é possível vigiar colocando todas as torres de vigia dadas em locais diferentes. As posições onde as torres podem ser colocadas têm de ser números inteiros, todas as torres têm de ser colocadas e em cada posição não pode haver mais do que uma torre.

Exemplo de Input

2 1
6
8
10
5
1
2
3

Exemplo de Output

5

Final Nacional das ONI'2008
Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto
(16 de Maio de 2008)