uCoder | 1098 | Nível: 4 | Tempo Limite: 10
Bolsa de valores
Adaptado por Erich Rodrigues
Competição: SBC - ACM/ICPC - Maratona de Programação de 2015
Um investidor principiante deseja aprender a investir na bolsa de valores. Como ele não tem experiência, selecionou uma única empresa, e acompanhou os valores diários das ações dessa empresa, durante N dias. Ficou curioso quanto teria ganhado se tivesse investido nesse período em que acompanhou os valores. Na verdade, o investidor é milionário e tem muito dinheiro, suficiente para comprar qualquer quantidade de ações da empresa. Entretanto, como é um investidor cuidadoso, decidiu que nunca teria mais do que uma ação da empresa.
Como sempre há intermediários, a corretora de valores cobra uma taxa fixa de C reais a cada compra de uma ação da empresa.
Você deve calcular qual o lucro máximo que o investidor poderia ter auferido, investindo durante alguns dos N dias, podendo inclusive decidir não investir.
Entrada
A primeira linha contém dois inteiros, N e C (1 ≤ N ≤ 2 × 105 e 0 ≤ C ≤ 30).
A segunda linha contém as N cotações P1 , P2 , . . . , PN , dos dias 1, 2, . . . , N , respectivamente. Cada cotação Pi satisfaz as desigualdades 1 ≤ Pi ≤ 1000.
Saída
Seu programa deve produzir uma única linha com um inteiro representando o lucro máximo do investidor, em reais.
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
13 30 |
220 |
|
5 10 |
0 |
|
6 10 |
20 |