// A one-day teaching model, not an AIRCONTECH judge submission.
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
struct Job { int x,y,service,reward; };
struct State {
    int x=0,y=0,minute=0,score=0,key=0,mask=0;
    vector<int> path;
};
bool betterAnswer(const State &a,const State &b) {
    if (a.score!=b.score) return a.score>b.score;
    if (a.minute!=b.minute) return a.minute<b.minute;
    return a.path<b.path;
}
int main() {
    int n,budget,width,penalty;
    if (!(cin>>n>>budget>>width>>penalty) || n<1 || n>12 || budget<1 || budget>1000 || width<1 || width>256 || penalty<0 || penalty>100) return 1;
    vector<Job> jobs(n);
    for (auto &j:jobs) {
        if (!(cin>>j.x>>j.y>>j.service>>j.reward) || j.x<0 || j.x>100 || j.y<0 || j.y>100 || j.service<1 || j.service>100 || j.reward<0 || j.reward>1000) return 1;
    }
    State best;
    vector<State> beam(1);
    for (int depth=0;depth<n && !beam.empty();++depth) {
        vector<State> candidates;
        for (const auto &state:beam) for (int i=0;i<n;++i) {
            if (state.mask & (1<<i)) continue;
            const auto &j=jobs[i];
            int minute=state.minute+abs(j.x-state.x)+abs(j.y-state.y)+j.service;
            if (minute>budget) continue;
            State next=state;
            next.x=j.x; next.y=j.y; next.minute=minute;
            next.score+=j.reward; next.key=next.score-penalty*minute;
            next.mask|=1<<i; next.path.push_back(i);
            // Consider the actual score BEFORE pruning, at every depth.
            if (betterAnswer(next,best)) best=next;
            candidates.push_back(next);
        }
        sort(candidates.begin(),candidates.end(),[](const State &a,const State &b) {
            if (a.key!=b.key) return a.key>b.key;
            return betterAnswer(a,b);
        });
        if ((int)candidates.size()>width) candidates.resize(width);
        beam=std::move(candidates);
    }
    cout<<best.score<<' '<<best.minute<<'\n';
    for (int i=0;i<(int)best.path.size();++i) cout<<(i?" ":"")<<best.path[i];
    cout<<'\n';
}