using System;
using System.Linq;

namespace TestCodility1
{
    class Program
    {
        public static int move(int[] positions, int[] knownCosts, int maxHop, int start)
        {
            var minCost = int.MaxValue;

            for (var i = 1; minCost != 0 && i <= maxHop; ++i)
            {
                var pos = start + i;
                if (pos >= positions.Length)
                {
                    minCost = 0;
                }
                else if (knownCosts[pos] >= 0)
                {
                    minCost = Math.Min(minCost, knownCosts[pos]);
                }
                else if (positions[pos] >= 0)
                {
                    var cost = move(positions, knownCosts, maxHop, pos);
                    if (cost >= 0)
                    {
                        cost = Math.Max(positions[pos], cost);

                        minCost = Math.Min(minCost, cost);

                        knownCosts[pos] = minCost;
                    }
                }
            }

            return minCost == int.MaxValue ? -1 : minCost;
        }

        public static int solution(int[] A, int D)
        {
            var knownCosts = Enumerable.Range(0, A.Length).Select(v => -1).ToArray();

            return move(A, knownCosts, D, -1);
        }

        static void CheckSolution(int[] A, int D, int expected)
        {
            var result = solution(A, D);
            if (result != expected)
            {
                var msg = $"{expected} != {result}";
                Console.WriteLine(msg);
                throw new Exception(msg);
            }
        }

        static void Main(string[] args)
        {
            CheckSolution(new[] { 0 }, 1, 0);
            CheckSolution(new[] { 3, 2, 1 }, 1, 3);
            CheckSolution(new[] { 2 }, 1, 2);
            CheckSolution(new[] { 1, -1, 0, 2, 3, 5 }, 3, 2);
            CheckSolution(new[] { 1, -1, -1, 3, 2, 5 }, 3, 3);
            CheckSolution(new[] { -1, -1, -1, 3, 2, 5 }, 3, -1);
            CheckSolution(new[] { -1, -1, -1, 3, 2, 5 }, 4, 3);
            CheckSolution(new[] { -1, -1, -1, 3, 2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }, 4, 17);
            CheckSolution(new[] { -1, -1, -1, 3, 2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 }, 5, 26);
        }
    }
}