Score : 100 points
There are N stones, numbered 1, 2, \ldots, N. For each i (1 \leq i \leq N), the height of Stone i is h_i.
There is a frog who is initially on Stone 1. He will repeat the following action some number of times to reach Stone N:
Find the minimum possible total cost incurred before the frog reaches Stone N.
Input is given from Standard Input in the following format:
N K h_1 h_2 \ldots h_N
Print the minimum possible total cost incurred.
5 3 10 30 40 50 20
30
If we follow the path 1 → 2 → 5, the total cost incurred would be |10 - 30| + |30 - 20| = 30.
3 1 10 20 10
20
If we follow the path 1 → 2 → 3, the total cost incurred would be |10 - 20| + |20 - 10| = 20.
2 100 10 10
0
If we follow the path 1 → 2, the total cost incurred would be |10 - 10| = 0.
10 4 40 10 20 70 80 10 20 70 80 60
40
If we follow the path 1 → 4 → 8 → 10, the total cost incurred would be |40 - 70| + |70 - 70| + |70 - 60| = 40.