13596번 - Bolsa de Valores 다국어

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.

A primeira linha contém dois inteiros, N e C (1 ≤ N ≤ 2 × 10⁵ e 0 ≤ C ≤ 30).

A segunda linha contém as N cotações P₁, P₂, . . . , P_N , dos dias 1, 2, . . . , N, respectivamente. Cada cotação P_i satisfaz as desigualdades 1 ≤ P_i ≤ 1000.

Seu programa deve produzir uma única linha com um inteiro representando o lucro máximo do investidor, em reais.