Crossing the Stepping Stones (small)

Interview

Time limit1sMemory limit1024 MB

Summary

Given stones with values A_i, decide if you can reach the last stone when each jump i to j costs (j-i)*(1+|A_i-A_j|) and no jump may exceed K.

Level: Medium5 of 10
Topics: Dynamic programming, Array, Implementation, Brute force
Solved: No attempts yet

Problem

$N$ stones are arranged in a line. The stones are given the numbers $A_{1}, A_{2}, ..., A_{i}, ..., A_{N}$ from left to right. You want to cross from the leftmost stone to the rightmost stone.

You can only move to the right.
Moving from the $i$ -th stone to the $j$ -th stone $(i < j)$ costs $(j - i) \times (1 + |A_{i} - A_{j}|)$ energy.
For each crossing between stones, you can use at most $K$ energy.

Determine whether you can cross from the leftmost stone to the rightmost stone.

Input

The first line gives the number of stones $N$ and the maximum energy $K$ you can use, separated by a space.

The second line gives the numbers $A_{i}$ of the $N$ stones, separated by spaces.

Output

If you can move to the rightmost stone, print YES. If you cannot, print NO.

Constraints

$2 \le N \le 5,000$
$1 \le K \le 1,000$
$1 \le A_{i} \le 1,000$
$A_{i}$ is an integer
$K$ is an integer

Examples2

Example 1
Input
```
5 3
1 4 1 3 1
```
Expected output
```
YES
```
Example 2
Input
```
5 3
1 5 2 1 6
```
Expected output
```
NO
```