#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <random>

using std::cout;
using std::cin;
using std::vector;
using std::endl;

int MinValueOf(int a, int b)
{
    return (a < b) ? a : b;
}
int BuyingApple(vector<int> PriceaTag, int Friends, int KilogramsToBuy)
{
    vector<vector<int>> Table(Friends + 1, vector<int>(KilogramsToBuy + 1, 0));
    for (int i = 1; i <= Friends; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            Table.at(i).at(j) = INT32_MAX;
            if (j == 0)
                Table[i][0] = 0;
            else if (PriceaTag[j] > 0)
                Table[i][j] = MinValueOf(Table[i][j], Table.at(i - 1).at(i - j) + PriceaTag.at(j));
        }
    }
    return (Table[Friends][KilogramsToBuy] == 0) ? -1 : Table[Friends][KilogramsToBuy];
}

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> distrib(-1, 1000);
    std::uniform_int_distribution<> distribNK(1, 100);
    std::uniform_int_distribution<> distribPos(1, 1000);
    int Friends;
    int Kilogram;
    vector<int> Price;
    while (true)
    {
        try
        {
            Friends = distribNK(gen);
            Kilogram = distribNK(gen);
            Price = std::vector<int>(Kilogram + 1, 0);
            std::generate(Price.begin() + 1, Price.end(), [&]() { return distrib(gen); });
            std::transform(Price.begin() + 1, Price.end(), Price.begin() + 1, [&](int n)
                { if (n == 0) return distribPos(gen);  return n; });
            std::cout << BuyingApple(Price, Friends, Price.size() - 1) << std::endl;
        }
    	catch (std::out_of_range& rError)
    	{
    		std::cout << rError.what() << "\n";
    		std::cout << "The following tests cause an issue:\n\n";
            std::cout << "Friends = " << Friends << "\nK = " << Kilogram << "\nPrice data:\n";
            int i = 0;
            for (auto p : Price)
            {
                std::cout << "[" << i << "]: " << p << "\n";
                ++i;
            }
            return 0;
    	}
    }
}