Minimum Cost to Reach Point n

Problem Statement

Minimum Cost to Reach Point n There are n points on the x-axis, labelled 1, 2, ..., n . You start standing at point 0 , which costs nothing. You are given an array cost of n integers, where cost[i - 1] is the price of landing on point i . From the point you are currently standing on, call it x , you may jump to any point y with x < y <= x + k . In other words a jump moves forward by at least 1 and at most k points. Every time you land on a point you pay that point's price. The total price of a journey is the sum of the prices of all the points you land on. Print the smallest total price of a journey that starts at point 0 and finishes standing on point n . Input Format Line 1: a single integer n , the number of points. Line 2: n space-separated integers cost[0] cost[1] ... cost[n - 1] . Line 3: a single integer k , the largest jump length. Output Format Print a single integer -- the smallest total price of a journey from point 0 to point n . Constraints 1 <= n <= 99000