수상한 주식

부패는 언제나 증명하기가 매우 어렵습니다. 누군가 뇌물을 받는다는 사실을 알더라도, 목격자는 뇌물을 받은 사람과 건넨 사람뿐이고 어느 쪽도 증언하려 하지 않기 때문에 처벌하기란 거의 불가능합니다.

불법이 있었음을 증명하는 한 가지 방법은 어떤 사람이 가진 돈을 세어 본 뒤, 그 돈을 합법적으로는 벌 수 없었음을 보이는 것입니다. 하지만 이는 쉽지 않습니다. 그 사람은 삼촌에게서 받은 돈이라거나 주식 거래로 번 돈이라고 얼마든지 둘러댈 수 있기 때문입니다.

우리는 이런 해명을 검증하고자 합니다. "삼촌"의 존재는 확인할 수 없으므로, 주식에 집중하겠습니다. 어떤 주식의 가격 기록이 주어질 때, 그 주식을 한 번 사고 한 번 팔아서 얻을 수 있는 최대 이익을 구하세요.

입력은 여러 개의 시나리오로 이루어집니다. 각 시나리오는 두 줄로 주어집니다.

첫째 줄에는 두 양의 정수 $D$와 $M$이 공백으로 구분되어 주어집니다 ($1 \le D \le 70000$, $1 \le M \le 40000$). $D$는 거래가 이루어진 날의 수이고, $M$은 처음에 가진 돈의 액수입니다.

둘째 줄에는 $D$개의 양의 정수 $p_1, p_2, \ldots, p_D$가 공백으로 구분되어 주어집니다 ($1 \le p_i \le 40000$). $p_i$는 $i$번째 날 주식 한 주의 가격이며, 그 날에는 한 주를 그 가격에 사거나 팔 수 있습니다.

마지막 시나리오 다음에는 $0$ 하나만 있는 줄이 옵니다.

각 시나리오마다, 최대 한 번의 매수 후 최대 한 번의 매도로 얻을 수 있는 최대 이익을 한 줄에 하나의 수로 출력하세요. 처음에는 주식을 하나도 갖고 있지 않으며, 전체 기간 동안 매수는 단 한 번만 할 수 있다고 가정합니다.

가진 돈으로 살 수 있는 만큼 여러 주를 살 수 있지만, 주식은 분할할 수 없으며 오직 정수 개수만큼만 사고팔 수 있습니다. 예를 들어 한 주의 가격이 $3이고 가진 돈이 $11이라면, 3주만 살 수 있습니다.

매수 이후에는 반드시 이후의 어느 날에 정확히 한 번의 매도가 이어집니다. 당연히 이익을 최대화하려면 보유한 주식을 모두 파는 것이 좋습니다.