1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <cstdlib>

typedef struct{int c; int m; int p;} type;

int asc(const void *a, const void *b)
{
  int c = ((type *)a)->c - ((type *)b)->c;
  int m = ((type *)a)->m - ((type *)b)->m;
  int p = ((type *)a)->p - ((type *)b)->p;
  return c+(c==0)*(m+(m==0)*p);
}

type t[7000];
long a[7000], b[7000];

int main()
{
  int n, c, m, k=0;
  scanf("%i%i%i", &n, &c, &m);
  for (int i = 0; i<n; i++) scanf("%i%i%i", &t[i].c, &t[i].m, &t[i].p);
  qsort(t, n, sizeof(*t), asc);
  for (int j = 0; j<m; j++) a[j] = -(j>0);
  for (int i = 0; i<n; i++)
  {
    if (t[i].c>k+1) break;
    if (t[i].c>k) for (int j = 0; j<m; j++) b[j] = a[j], a[j] = -1;
    for (int j = 0; j<m; j++) if (b[j]>=0) if (a[(j+t[i].m)%m]<0 || a[(j+t[i].m)%m]>b[j]+t[i].p) a[(j+t[i].m)%m] = b[j]+t[i].p;
    k = t[i].c;
  }
  if (k<c)
  {
    for (int j = 0; j<m; j++) printf("%i\n", -(j>0));
    return 0;
  }
  a[0] = 0;
  while (k>0)
  {
    k = 0;
    for (int i = 0; i<m; i++) for (int j = 0; j<m; j++) if (a[i]>=0 && a[j]>=0) if (a[(i+j)%m]<0 || a[(i+j)%m]>a[i]+a[j]) a[(i+j)%m] = a[i]+a[j], k = 1;
  }
  for (int j = 0; j<m; j++) printf("%li\n", a[j]);
  return 0;
}