Descrição
Carlão é muito preocupado com o meio ambiente. Sempre que possível, ele tenta utilizar meios de transporte menos poluentes. Recentemente ele conseguiu um emprego próximo de casa e agora está utilizando sua bicicleta para ir ao trabalho.
Infelizmente, no caminho entre sua casa e seu emprego, há uma fábrica de pregos, que frequentemente deixa alguns pregos caírem de seus caminhões que acabam furando os pneus de da bicicleta de Carlão. Por isso, ele acaba tendo que fazer diversos remendos nos pneus de sua bicicleta.
Para fazer os consertos, Carlão usa dois tipos diferentes de remendos. Ambos os tipos têm a largura do pneu da bicicleta, mas diferem no comprimento. Como o valor do remendo é proporcional ao seu comprimento, Carlão está tentando encontrar uma maneira de economizar, gastando o menor comprimento total possível de remendos para fazer os consertos, mas sem precisar cortá-los.
O primeiro passo para efetuar o conserto é fazer uma marca com giz em uma posição do pneu e depois anotar as distâncias, medidas no sentido horário, de cada um dos furos em relação à marca de giz. Todos os furos devem ser cobertos por um remendo. Carlão gostaria de sua ajuda para determinar, a partir das posi¸cões dos furos, a forma mais econômica de efetuar o conserto.
Entrada
A entrada consiste de duas linhas. A primeira linha contém quatro inteiros N, C, T1 e T2 . O inteiro N corresponde ao número de furos no pneu e C corresponde ao comprimento da circunferência do pneu, em centı́metros. Os comprimentos dos remendos, em centı́metros, são dados pelos inteiros T1 e T2 . A segunda linha da entrada contém N inteiros Fi , um para cada furo, descrevendo a distância no sentido horário da marca de giz até o furo i, em centı́metros.
Saída
Seu programa deve imprimir uma única linha contendo um inteiro indicando o menor comprimento total de remendos que é suficiente para consertar todos os furos do pneu.
Restrições
• 1 ≤ N ≤ 1000
• 1 ≤ C ≤ 106
• 1 ≤ T1 , T2 ≤ C
• 0 ≤ Fi ≤ C − 1, 1 ≤ i ≤ N
• Se a distância entre dois furos é exatamente k centı́metros, um remendo de comprimento k centı́metros é suficiente para cobrir ambos os furos.
| Exemplos de Entrada | Exemplos de Saída |
|---|---|
|
4 20 12 9 |
12 |
|
5 20 2 3 |
8 |
Efetue Login ou Cadastre-se para submeter uma solução.
Adaptado por Erich Rodrigues | Competição: Maratona de Programação da SBC 2013