시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

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 × 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.

출력

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

예제 입력 1

6 10
100 120 130 80 50 40

예제 출력 1

20

예제 입력 2

5 10
70 80 50 40 50

예제 출력 2

0

예제 입력 3

13 30
10 80 20 40 30 50 40 60 50 70 60 10 200

예제 출력 3

220