#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

const int inf = 1e9;

vector<int> r;
vector<int> d;
vector<int> p;
vector<int> w;
int n;
int t;

int penalty(int time, int j)
{
    if (time>d[j])
        return w[j];
    return 0;
}

void gen(int nn)
{
    int mod = 10;
    int wmod = 10;
    n = nn;
    t = rand()%mod+1;
    r.resize(n);
    d.resize(n);
    p.resize(n);
    w.resize(n);
    for (int i = 0; i<n; i++)
    {
        d[i] = p[i] = w[i] = r[i] =  0;
        if (i)
            r[i] = r[i-1];
        r[i] = r[i] + rand()%mod;

        d[i] = r[i] + rand()%mod+1;
        while (i && d[i]<d[i-1])
            d[i] = r[i] + rand()%mod+1;

        p[i] = rand()%(d[i]-r[i])+1;
        w[i] = rand()%wmod;
    }
}
void read()
{
    cin >> n >> t;
    r.resize(n);
    for (int i = 0; i<n; i++)
        cin >> r[i];
    d.resize(n);
    for (int i = 0; i<n; i++)
        cin >> d[i];
    p.resize(n);
    for (int i = 0; i<n; i++)
        cin >> p[i];
    w.resize(n);
    for (int i = 0; i<n; i++)
        cin >> w[i];

}
bool readfromfile()
{
    cout << "Введите путь к файлу: ";
    string s;
    cin >> s;
    ifstream fin(s);
    if (!(fin >> n >> t))
        return false;
    r.resize(n);
    for (int i = 0; i<n; i++)
        if (!(fin >> r[i]))
            return false;
    d.resize(n);
    for (int i = 0; i<n; i++)
        if (!(fin >> d[i]))
            return false;
    p.resize(n);
    for (int i = 0; i<n; i++)
        if (!(fin >> p[i]))
            return false;
    w.resize(n);
    for (int i = 0; i<n; i++)
        if (!(fin >> w[i]))
            return false;
    return true;
}

int calcT(vector<int> &v, int t, int without)
{
    int curtime = t;
    for (int i = 0; i<v.size(); i++)
    {
        if (v[i] == without)
            continue;

        curtime = max(curtime,r[v[i]]);
        curtime+= p[v[i]];

    }
    return curtime;
}
pair<vector<int>,vector<int>> algo()
{
    int curtime = t;
    vector<int> late,notlate;
    queue<int> todo;
    for (int i = 0; i<n; i++)
        todo.push(i);
    while (!todo.empty())
    {

        int i = todo.front();
        curtime = max(curtime,r[i]);
        if (curtime+p[i]<=d[i]) // если не запаздывает добавляем в множество незапаздывающих
        {
            notlate.push_back(i);
            curtime+=p[i];
            todo.pop();
        }
        else
        {
            int m = i;
            int mintime = INT_MAX;
            notlate.push_back(i);
            for (int j = 0; j<notlate.size(); j++)
            {
                int calct = calcT(notlate,t,notlate[j]);
                if (calct<mintime)
                {
                    m = j;
                    mintime = calct;
                }
            }
            notlate.pop_back();
            if (notlate[m] == i)
            {
                late.push_back(i);
                todo.pop();
            }
            else
            {
                late.push_back(notlate[m]);
                notlate.erase(notlate.begin()+m);
                curtime = calcT(notlate, t, inf);
            }
        }
    }
    return {notlate,late};
}
int calcF(vector<int> &late)
{
    int ans = 0;
    for (auto it:late)
        ans+=w[it];
    return ans;
}
void update(pair<vector<int>,vector<int>> &best, vector<int>&late, vector<int> &notlate)
{
    if (best.first.size()==0 && best.second.size()==0)
    {
        best = {notlate,late};
        return;
    }
    if (calcF(best.second)>calcF(late))
    {
        best = {notlate,late};
    }
}

pair<vector<int>,vector<int>> bestSol()
{
    vector<int> perm;
    for (int i = 0; i<n; i++)
    {
        perm.push_back(i);
    }

    pair<vector<int>,vector<int>> best;// первое значение незапаздывающие второе запаздывающие
    do
    {
        int curtime = t;
        vector<int> late,notlate;
        for (auto it:perm)
        {
            int i = it;
            curtime = max(curtime,r[i]);
            if (curtime+p[i]<=d[i])
            {
                notlate.push_back(i);
                curtime+=p[i];
            }
            else
            {
                late.push_back(i);
            }
        }
        update(best,late,notlate);
    }
    while (next_permutation(perm.begin(),perm.end()));
    return best;
}

pair<vector<int>,vector<int>> algo1()// не учитываем веса, если не нашлось требования удовлетворяющее двум условиям
{
    int curtime = t;    // tk
    vector<int> late,notlate;// П1, П2
    queue<int> todo;// Nk
    for (int i = 0; i<n; i++)
        todo.push(i);
    while (!todo.empty())
    {

        int i = todo.front();
        curtime = max(curtime,r[i]);
        if (curtime+p[i]<=d[i]) // если не запаздывает добавляем в множество незапаздывающих
        {
            notlate.push_back(i);
            curtime+=p[i];
            todo.pop();// удаление из очереди
        }
        else
        {
            int mintimeind = 0;
            int minwind = 0;
            notlate.push_back(i);   // добавить конец
            vector<pair<int,int>> forcalc(notlate.size());

            for (int j = 0; j<notlate.size(); j++)
            {
                forcalc[j] = {calcT(notlate,t,notlate[j]),w[notlate[j]]};
                if (forcalc[mintimeind].first>forcalc[j].first)
                    mintimeind = j;
                if (forcalc[minwind].second>forcalc[j].second)
                    minwind = j;
            }

            int m = -1;

            for(int j = 0; j<notlate.size(); j++)
                if (forcalc[j].first == forcalc[mintimeind].first && forcalc[j].second == forcalc[minwind].second)
                    m = j;

            if (m==-1)// тут мы не смогли найти требование которое удовлетворяет двум условиям, берем то у которого минимальное время и среди всех таких мин вес
            {
                m = mintimeind;
                for (int j = 0; j<notlate.size(); j++)
                    if (forcalc[j].first == forcalc[m].first && forcalc[j].second<forcalc[m].second)
                        m = j;
            }

            if (notlate[m] == i)
            {
                notlate.pop_back();// удалить с конца

                late.push_back(i);
                todo.pop();
            }
            else
            {
                notlate.pop_back();// удалить с конца

                late.push_back(notlate[m]);
                notlate.erase(notlate.begin()+m);
                curtime = calcT(notlate, t, inf);
            }
        }
    }
    return {notlate,late};
}


pair<vector<int>,vector<int>> algo2()// учитываем веса, если не нашлось требования удовлетворяющее двум условиям
{
    int curtime = t;
    vector<int> late,notlate;
    queue<int> todo;
    for (int i = 0; i<n; i++)
        todo.push(i);
    while (!todo.empty())
    {

        int i = todo.front();
        curtime = max(curtime,r[i]);
        if (curtime+p[i]<=d[i]) // если не запаздывает добавляем в множество незапаздывающих
        {
            notlate.push_back(i);
            curtime+=p[i];
            todo.pop();
        }
        else
        {
            int mintimeind = 0;
            int minwind = 0;
            notlate.push_back(i);
            vector<pair<int,int>> forcalc(notlate.size());

            for (int j = 0; j<notlate.size(); j++)
            {
                forcalc[j] = {calcT(notlate,t,notlate[j]),w[notlate[j]]};
                if (forcalc[mintimeind].first>forcalc[j].first)
                    mintimeind = j;
                if (forcalc[minwind].second>forcalc[j].second)
                    minwind = j;
            }

            int m = -1;

            for(int j = 0; j<notlate.size(); j++)
                if (forcalc[j].first == forcalc[mintimeind].first && forcalc[j].second == forcalc[minwind].second)
                    m = j;
            if (m==-1)// тут мы не смогли найти требование которое удовлетворяет двум условиям, берем то у которого мин вес и среди всех таких мин время
            {
                m = minwind;
                for (int j = 0; j<notlate.size(); j++)
                    if (forcalc[j].second == forcalc[m].second && forcalc[j].first<forcalc[m].first)
                        m = j;
            }

            if (notlate[m] == i)
            {
                notlate.pop_back();

                late.push_back(i);
                todo.pop();
            }
            else
            {
                notlate.pop_back();

                late.push_back(notlate[m]);
                notlate.erase(notlate.begin()+m);
                curtime = calcT(notlate, t, inf);
            }
        }
    }
    return {notlate,late};
}

bool issled = false;
int bettersolution[2];
void solve(int disp)
{
    // debug();
    auto ans = algo();
    if (disp)
    {
        cout << "Результат работы алгоритма из лекции\n";
        cout << "Незапаздывающие: ";
        for (auto it: ans.first)
            cout << it+1 << " ";
        cout << endl << "Запаздывающие: ";
        for (auto it:ans.second)
            cout << it+1 << " ";

        cout << "\nСумма весов запаздывающих: " << calcF(ans.second) << endl << endl;
    }

    auto ans1 = algo1();
    if (disp)
    {
        cout << "Результат работы алгоритма с учетом первого условия\n";
        cout << "Незапаздывающие: ";
        for (auto it: ans1.first)
            cout << it+1 << " ";
        cout << endl << "Запаздывающие: ";
        for (auto it:ans1.second)
            cout << it+1 << " ";

        cout << "\nСумма весов запаздывающих: " << calcF(ans1.second) << endl << endl;
    }
    auto ans3 = algo2();
    if (disp)
    {
        cout << "Результат работы алгоритма с учетом второго условия\n";
        cout << "Незапаздывающие: ";
        for (auto it: ans3.first)
            cout << it+1 << " ";
        cout << endl << "Запаздывающие: ";
        for (auto it:ans3.second)
            cout << it+1 << " ";

        cout << "\nСумма весов запаздывающих: " << calcF(ans3.second) << endl << endl;

    }
    if (n<10)
    {
        auto ans2 = bestSol();
        if (disp)
        {
            cout << "Результат работы точного алгоритма\n";
            cout << "Незапаздывающие: ";
            for (auto it: ans2.first)
                cout << it+1 << " ";
            cout << endl << "Запаздывающие: ";
            for (auto it:ans2.second)
                cout << it+1 << " ";

            cout << "\nСумма весов запаздывающих: " << calcF(ans2.second) << endl;
        }
    }
    if (issled)
    {
        int second = calcF(ans3.second);
        int first = calcF(ans1.second);
        int best = min(first,second);
        if (first == best)
        {
            bettersolution[0]++;
            if (disp)
            {
                cout << "Алгоритм с учетом первого условия хорошо отработал для данной задачи\n";
            }
        }
        if (second == best)
        {
            bettersolution[1]++;
            if (disp)
            {
                cout << "Алгоритм с учетом второго условия хорошо отработал для данной задачи\n";
            }
        }
    }

}

void display()
{
    cout << "N = " << n << " t = "<< t << endl;
    cout << "r = ";
    for (int i = 0; i<n; i++)
        cout << r[i] << " ";
    cout << endl;
    cout << "d = ";
    for (int i = 0; i<n; i++)
        cout << d[i] << " ";
    cout << endl;
    cout << "p = ";

    for (int i = 0; i<n; i++)
        cout << p[i] << " ";
    cout << endl;
    cout << "w = ";
    for (int i = 0; i<n; i++)
        cout << w[i] << " ";
    cout << endl;
}
int get_command()
{
    int x = -1;
    while (x<0 || x>3)
    {
        cout << "Введите 1 для проведения иследование\n        2 для ввода данных с файла\n        3 для ввода данных вручную\n        0 для выхода\n";
        cin >> x;
    }
    return x;
}
void make_isledovanie()
{
    issled = true;
    cout << "Введите количество тестов: ";
    int tests;
    cin >> tests;

    int disp = 2;
    while (disp!=0 && disp!=1)
    {
        cout << "Для просмотра решения каждого примера нажмите 1, иначе 0: ";
        cin >> disp;
    }

    int nn = 25;// размерность количества требования при генерации (N) ЭТО НАДО МЕНЯТЬ ДЛЯ ИССЛЕДОВАНИЯ
    bettersolution[0] = bettersolution[1] = 0;


    for (int i = 0; i<tests; i++)
    {
//        if(i%5==0)
//            nn+=5;
        gen(nn);
        if (disp)
            display();
        solve(disp);
    }
    cout << "Алгоритм с учетом первого условия для размерности " << nn << " хорошо отработал для "<< bettersolution[0]*100.0/tests<<"% задач\n";
    cout << "Алгоритм с учетом второго условия для размерности " << nn << " хорошо отработал для "<< bettersolution[1]*100.0/tests<<"% задач\n";
    cout << endl;

    issled = false;
}

int main()
{
    srand(time(0));
    while (true) {
        int x = get_command();
        if (x==0)
            break;
        if (x==1)
        {
            make_isledovanie();
        }
        else if (x == 2)
        {
            bool readed = readfromfile();
            if (!readed)
            {
                cout << "Неправильный путь или неверные входные данные в файле. Повторите еще раз";
                continue;
            }
            display();
            solve(1);
        }
        else
        {
            read();
            solve(1);
        }
    }

}