#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int N, T;

int AD[1050];
struct Employee{
    int a, b, c, id;
};
vector<Employee> E[550];

int num=1;
int VL[550], VU[550];
int LV[1050], UV[1050];

struct FlowEdge{
    int to, cap, rev;
};
vector<FlowEdge> adj[550];

// 0: source, 1: sink
void add_edge(int u, int v, int cap){
    adj[u].push_back({v, cap, (int)adj[v].size()});
    adj[v].push_back({u, 0, (int)adj[u].size()-1});
}

int ans=0;

bool vis[550];
int FF(int u, int flow){
    if (u == 1) return flow;
    vis[u] = true;
    for (FlowEdge &e: adj[u]){
        if (e.cap > 0 && !vis[e.to]){
            int f = FF(e.to, min(flow, e.cap));
            if (f > 0){
                e.cap -= f;
                adj[e.to][e.rev].cap += f;
                return f;
            }
        }
    }
    return 0;
}

bool selected[550];
void check(int u){
    if (vis[u]) return;
    vis[u] = true;
    selected[VL[u]] = !selected[VL[u]];
    selected[VU[u]] = !selected[VU[u]];
    for (FlowEdge &e: adj[u]){
        if (e.cap > 0) check(e.to);
    }
}

int main() {
    scanf("%d %d", &N, &T);
    for (int i=1; i<=N; i++){
        int a, b, c, d;
        scanf("%d %d %d %d", &a, &b, &c, &d);
        E[d].push_back({a, b, c, i});
        AD[a] = d;
    }

    for (int i=1; i<=T; i++){
        sort(E[i].begin(), E[i].end(), [](const Employee &x, const Employee &y){
            return x.a < y.a;
        });
        for (int j=1; j<E[i].size(); j++){
            ++num;
            VL[num] = E[i][j-1].id, LV[E[i][j-1].a] = num;
            VU[num] = E[i][j].id, UV[E[i][j].a] = num;

            if (E[i][j].b > E[i][j-1].b){
                ans += E[i][j].b - E[i][j-1].b;
                add_edge(0, num, E[i][j].b - E[i][j-1].b);
            }
            else if (E[i][j].b < E[i][j-1].b) add_edge(num, 1, E[i][j-1].b - E[i][j].b);

            if (j == 1) add_edge(num, 1, E[i][j-1].c);
            if (j > 1) {
                add_edge(num-1, num, E[i][j-1].c);
                add_edge(num, num-1, E[i][j-1].c);
            }
            if (j == E[i].size()-1) add_edge(num, 1, E[i][j].c);
        }
    }
    for (int i=1; i<=T+1; i++){
        vector<int> na;
        for (Employee e: E[i-1]) na.push_back(e.a);
        for (Employee e: E[i]) na.push_back(e.a);
        sort(na.begin(), na.end());

        int l=0, r=0;
        for (int j=0; j<na.size(); j++){
            if (j > 0 && (l || r)){
                if (!l) add_edge(r, 1, na[j]-na[j-1]);
                else if (!r) add_edge(l, 1, na[j]-na[j-1]);
                else {
                    add_edge(l, r, na[j]-na[j-1]);
                    add_edge(r, l, na[j]-na[j-1]);
                }
            }
            if (AD[na[j]] == i-1) l = LV[na[j]];
            else r = LV[na[j]];
        }
    }

    while (1){
        memset(vis, 0, sizeof(vis));
        int f = FF(0, 10000000);
        if (f == 0) break;
        ans -= f;
    }

    printf("%d\n", ans);
    memset(vis, 0, sizeof(vis));
    check(0);

    int cnt=0;
    for (int i=1; i<=N; i++) if (selected[i]) cnt++;
    printf("%d\n", cnt);
    for (int i=1; i<=N; i++) if (selected[i]) printf("%d ", i);
    puts("");

    return 0;
}