Education Reform

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct TSubject
{
    __int64 a, b;
    int nmb, c;
} sb[100];
bool operator < (const TSubject &x, const TSubject &y)
{
    return x.c < y.c;
}
int n, m, k, cur = 0;
__int64 d[50][101][51];
pair<int, int> p[50][101][51], state;
int main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < m; ++i)
    {
        cin >> sb[i].a >> sb[i].b >> sb[i].c;
        sb[i].nmb = i + 1;
    }
    sort(sb, sb + m);
    state = make_pair(0, 0);
    for (int i = 0; i < m; ++i)
        for (int j = 0; j <= sb[i].b - sb[i].a; ++j)
        {
            d[i][j][1] = sb[i].a + j;
            for (int z = 2; z <= n; ++z)
            {
                d[i][j][z] = -1;
                for (int last = i - 1; last >= 0; --last)
                    if (sb[last].c < sb[i].c)
                        for (int t = 0; t <= 1; ++t)
                        {
                            __int64 temp = sb[i].a + j;
                            bool yes = (t == 0) ? temp % k == 0 : temp >= k;
                            temp = (t == 0) ? temp / k : temp - k;
                            temp -= sb[last].a;
                            if (!yes) continue;
                            if (temp >= 0 && temp <= sb[last].b - sb[last].a
                                && d[last][temp][z - 1] != -1
                                && d[last][temp][z - 1] + sb[i].a + j > d[i][j][z])
                            {
                                d[i][j][z] = d[last][temp][z - 1] + sb[i].a + j;
                                p[i][j][z] = make_pair(last, temp);
                            }
                        }
            }
            if (d[i][j][n] > d[state.first][state.second][n])
                state = make_pair(i, j);
        }
    if (d[state.first][state.second][n] == -1)
    {
        cout << "NO";
        return 0;
    }
    vector<pair<int, __int64> > ans;
    for (int i = n; i >= 1; --i)
    {
        ans.push_back(make_pair(sb[state.first].nmb, sb[state.first].a + state.second));
        state = p[state.first][state.second][i];
    }
    cout << "YES" << endl;
    for (int i = n - 1; i >= 0; --i)
        cout << ans[i].first << ' ' << ans[i].second << endl;
    return 0;
}