見習魔法師宜恩最近在和他的師父芒果學習水果魔法,他們現在在山上修練。
具體來說,有 $N$ 座山排成一列,由左數來的第 $i$ 座山的高度為 $a_i$,宜恩一開始在第 $1$ 座山上,總共有 $K$ 點魔力值,他的目標是抵達第 $N$ 座山越快越好,這樣他就可以去刷題了。
當宜恩在第 $i$($1\le i<n$) 座山時他可以做兩種事:
宜恩很好奇他需要多少時間才能抵達第 $N$ 座山,請你幫幫他!
第一行會有兩個整數 $N$, $K$,代表一共有幾座山跟宜恩的魔力值。
第二行會有一個陣列 $a_1\sim a_N$,代表每座山的高度。
對於所有測試資料:
輸出一個整數,表示宜恩最少需要花多少時間才能抵達第 $N$ 座山。
範例測資 1 解釋:其中一種最少時間的方法會使山最後變成$4$ $4$ $5$ $2$ $3$
範例測資 2 解釋:其中一種最少時間的方法會使山最後變成$6$ $5$ $4$ $4$ $7$
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資 | 0 |
2 | 0~12 | $N\leq 5000,K\le 2\times 10^ 7,a_i\leq 5000$($1\leq i\leq N$) | 28 |
3 | 1~6, 12~21 | $\exists i$($1\leq i\leq N$)使得 $a_j\geq a_{j+1}$($1\leq j< i$),$a_j\leq a_{j+1}$($i\leq j<N$) | 25 |
4 | 0~41 | 無其他限制 | 47 |