Problema B - Trabalhadores em linha

Na fábrica das ONI criam-se muitos problemas para poderem ser resolvidos por concorrentes como tu. No entanto, é preciso alguém verificá-los para garantir que não têm nenhum erro e assim poderem ser usados em provas futuras. Para isto, a fábrica tem uma linha de N trabalhadores. Os seus postos de trabalho são seguidos e por ordem, isto é, o posto do trabalhador i está logo a seguir ao do i-1 e antes do i+1 (o primeiro e último trabalhador têm apenas um vizinho).

Cada trabalhador tem uma pilha de problemas para verificar, mas, como é óbvio, cada trabalhador é diferente e tem métodos de trabalho diferentes, logo demora um tempo diferente a verificar cada problema. Assim, o trabalhador i demora P_i segundos a verificar um problema. Além de verificar um problema que tenha na sua pilha, um trabalhador pode alternativamente entregá-lo ao trabalhador imediatamente a seguir na linha de trabalhadores (o trabalhador i pode entregar problemas apenas ao trabalhador i + 1). Notem que o último trabalhador, o de índice N, não tem ninguém para entregar um problema, por isso tem de verificar todos os problemas que tiver na sua pilha ele mesmo. Para isto, cada trabalhador demora os mesmos Q segundos.

Cada trabalhador pode escolher fazer uma das seguintes ações sempre que está livre: processar um problema que tenha na sua pilha de problemas, demorando P_i segundos para completar esta ação; ou entregar um problema que tenha na sua pilha de problemas ao seu vizinho (se puder), demorando Q segundos para completar esta ação. Assim que um trabalhador completa uma ação, está novamente livre. Inicialmente, todos os trabalhadores estão livres. Se um trabalhador estiver livre e não tiver nenhum problema na sua pilha de problemas, espera até que lhe seja entregue um ou que todos os problemas sejam processados.

Este ano há K problemas para serem verificados. Inicialmente, os K problemas são colocados na pilha do primeiro trabalhador. Vejamos um exemplo de um possível estado da fábrica das ONI e vejamos como podem proceder os trabalhadores:

Neste exemplo temos 3 problemas que inicialmente se encontram na pilha do primeiro trabalhador. O trabalhador 1 começa por entregar um problema para o trabalhador 2, demorando 1 segundo no processo. Assim que termina, o trabalhador 2 começa a verificar esse problema demorando 3 segundos. Entretanto o trabalhador 1 entrega mais um problema para o trabalhador 2, demorando mais 1 segundo. Porém, quando este problema chega à pilha do trabalhador 2, este ainda se encontra a trabalhar no primeiro problema que recebeu, por isso não pode verificá-lo imediatamente. Finalmente, o trabalhador 1 verifica o último problema que lhe resta na pilha, demorando 5 segundos a fazê-lo, e o trabalhador 2, após terminar a verificação do primeiro problema, verifica o segundo, demorando 3 segundos a fazê-lo.

No total o trabalhador 1 demora 2 segundos a entregar problemas e 5 a verificar um. O trabalhador 2 espera 1 segundo para receber o primeiro problema e depois demora 6 segundos a verificar os dois problemas que recebe. O trabalhador 3 fica o tempo todo à espera e não faz trabalho nenhum. No total, passaram 7 segundos até os problemas terem sido todos verificados. Não é difícil de ver que esta é a forma mais rápida de verificar os 3 problemas.

Ultimamente a fábrica tem andado com problemas de eficiência, e, com o aproximar da IOI (International Olympiad in Informatics), precisa mais do que nunca de produzir problemas para que os representantes de Portugal possam ser selecionados. Para isso a fábrica precisa da tua ajuda para encontrar o menor tempo possível necessário para verificar todos os problemas.

O Problema

Dado o número N de trabalhadores, K de problemas que estão inicialmente na posse do primeiro trabalhador, o valor P_i do tempo que cada trabalhador demora a verificar um problema e o tempo Q que demora cada trabalhador a entregar um problema ao próximo, calcula o menor tempo possível no qual se conseguem verificar todos os problemas.

Input

Na primeira linha vêm 3 inteiros, o número N de trabalhadores, K que corresponde ao número de problemas inicialmente no posto do primeiro trabalhador e Q segundos que demora a movimentar um problema de um posto para o próximo. As próximas N linhas têm um inteiro P_i, que é o tempo que o i-ésimo trabalhador demora a processar um problema.

Nota: É garantido que o valor de P_i é maior que Q para todos os trabalhadores i.

Output

Uma linha como o menor tempo possível para verificar K problemas

Nota: a resposta tem valor máximo 2⁶⁰

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Os casos de teste deste problema estão organizados em 6 grupos com restrições adicionais diferentes:

Input do Exemplo 1

3 3 1
5
3
4

Output do Exemplo 1

7

Explicação do Exemplo 1

Este exemplo corresponde ao mencionado no enunciado.

Input do Exemplo 2

3 12 0
4
1
3

Output do Exemplo 2

8

Input do Exemplo 3

2 5 2
7
5

Output do Exemplo 3

20

Input do Exemplo 4

4 2 1
10
5
7
3

Output do Exemplo 4

7