#include <cstdio>
#include <set>
#include <map>
#include <utility>
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;

#define mp make_pair
#define pb push_back
#define sz(a) int((a).size())
#define forn(i, n) for (int i=0; i<(n); ++i)

typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;

const int maxn = 128;

int f[maxn][maxn];
int p[maxn][maxn];
int num[maxn], l[maxn], d[maxn];
int n, m;

int main()
{
//  freopen("a.in", "r", stdin);

  for (int tc=1; ; ++tc)
  {
    scanf("%d %d", &m, &n);
    if (m == 0 && n == 0) break;
    forn (i, n)
      scanf("%d %d %d", num+i, l+i, d+i);
    forn (i, maxn) forn (j, maxn) f[i][j] = -1;
    f[0][0] = 0;
    forn (i, n) forn (j, m+1) if (f[i][j]!=-1)
    {
      for (int k=0; j+k<=m; ++k)
      {
        double cur = l[i]*0.01 + (k/(10.1+k)) * d[i] * 0.01;
        int add = cur*num[i]+0.5;
        if (f[i+1][j+k] <= f[i][j]+add)
          f[i+1][j+k] = f[i][j]+add, p[i+1][j+k] = k;
      }
    }

    int res = f[n][m];
    printf("Case %d: %d\n", tc, res);
    vector<int> ans;
    for (int i=n, j=m; i>0; --i)
    {
      ans.pb(p[i][j]);
      j -= p[i][j];
    }
    reverse(ans.begin(), ans.end());
    forn (i, sz(ans))
    {
      if (i) printf(" ");
      printf("%d:%d", i, ans[i]);
    }
    puts("");


  }

  return 0;
}