TopCoder

User's AC Ratio

100.0% (10/10)

Submission's AC Ratio

20.2% (18/89)

Tags

Description

「妁艷起床啦~~~~!」

妁艷勉強睜開眼睛,映入眼簾的是楓音那張充滿稚氣的臉。兩人的臉近到妁艷可以感覺到她呼出的氣息,妁艷連忙把她推開。

剛剛好像不小心昏過去了呢,不過話說回來,這裡是哪裡啊?妁艷心想。

「YA~妁艷醒來了~~~,」楓音坐在妁艷的腿上說道:「剛剛你在草地上昏過去了,所以我就把你搬到保健室來了。這裡的床很舒服吧~♥」

果然昏過去了,一定是今天晚上魔力什麼的消耗太多了。妁艷心想。

妁艷指著角色資料旁邊的魔力值看著楓音,「我需要補魔力了......。」

「好阿~,」楓音燦笑道:「可是為了補償我剛剛一個人很無聊,你要先陪我玩一個遊戲。」說話的同時,她拿出了一個長條型的棋盤以及M顆螢光綠的珠子。

為了盡快補完魔力找到妹妹,妁艷勉強的答應了。

遊戲規則如下:

(1) 棋盤是由N個排成一直線的格子組成的。格子由左到右邊號1~N,且每一格都有自己的高度。

(2) 在第1格有一個棋子,妁艷只能將棋子往編號大的格子移,目標是將棋子移到第N格。

(3) 用x[i]表示棋盤第i格的高度,則妁艷將棋子從第i格移到第j格(i < j)需要花max(0 , (j - i) + (x[j] - x[i]))單位的力氣。

(4) 妁艷每移動一次棋子,如果楓音手上還有珠子,她就會給他一顆。

「如果在你把棋子移到第N格的時候我手上沒有珠子了,就幫你補魔力吧~。」楓音提出條件。

因為妁艷不想花太多力氣在這個遊戲上,所以請告訴他,在花最少力氣的前提下最多可以得到幾顆珠子吧。

Input Format

第一行有兩個正整數N、M,代表棋盤的格數以及楓音一開始有的珠子數。
第二行有N個整數,第i個數代表棋盤第i格的高度。

2 ≤ N ≤ 300,000
M ≤ 109
|棋盤任一格子的高度| ≤ 109

Output Format

輸出一個正整數,代表妁艷在花最少力氣的前提下可以得到的珠子個數的最大值。

Sample Input

4 10
1 2 3 4

Sample Output

3

Hints

棋子的移動路徑:1 -> 2 -> 3 -> 4
總共移動3次,花了6單位的力氣。

Problem Source

原TIOJ1764 / problem setter : esrever

Subtasks

No. Testdata Range Score
1 0 11
2 1 11
3 2 11
4 3 11
5 4 11
6 5 11
7 6 11
8 7 11
9 8 12

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 4
4 2000 65536 262144 5
5 2000 65536 262144 6
6 2000 65536 262144 7
7 2000 65536 262144 8
8 2000 65536 262144 9