3_problem

#include <algorithm>
#include <climits>
#include <cstdio>
#include <vector>

#define N_PROBLEMS 6U
#define FIND_N_PROBLEMS ((unsigned char)exer.back().size() - 1)
#define I_PER 0U

struct problem {
  unsigned int a = 0; // sum of scores or score
  unsigned int b = 0; // id or number of submissions
};

std::vector<std::vector<problem>> exer;

unsigned int my_sum;

inline bool comp_exer(std::vector<problem>& i, std::vector<problem>& j) {
  return (i[I_PER].a < j[I_PER].a);
}

inline bool comp_exer1(const problem& i, const problem& j) {
  //if (i.a != j.a) {
  //  return (i.a > j.a);
  //} else {
  //  return (i.b < j.b);
  //}
  return (i.a > j.a);
}

inline unsigned int min_count_sum(void) {
  unsigned int min_count = UINT_MAX;
  problem sum;
  for (unsigned char enabled = 1;
       enabled < (1 << FIND_N_PROBLEMS); enabled++) {
    for (unsigned int i = 0; i < N_PROBLEMS; i++) {
      if ((enabled & (1 << i)) != 0) {
        sum.a += exer.back()[i + 1].a;
        sum.b += exer.back()[i + 1].b;
      }
    }
    if ((exer.back()[I_PER].a - sum.a) <= my_sum) {
      if (sum.b < min_count) {
        min_count = sum.b;
      }
    }
    sum.a = 0;
    sum.b = 0;
  }

  return min_count;
}

int main(void) {
  unsigned int n, q;
  scanf("%u", &n);
  scanf("%u", &q);

  exer.resize(n);

  for (unsigned int i = 0; i < n; i++) {
    exer[i].resize(1 + N_PROBLEMS);
    //exer[i][I_PER].a = 0; // score sum
    //exer[i][I_PER].b = i; // id
  }

  //  get input data
  unsigned int id, score, ex;
  char ex_c;
  for (unsigned int i = 0; i < q; i++) {
    scanf("%u", &id);
    id--;
    scanf(" %c", &ex_c);
    ex = (ex_c - 'A') + 1;
    scanf("%u", &score);

    if (exer[id][ex].a < score) {
      exer[id][ex].a = score;
    }
    exer[id][ex].b++;
  }

  for (unsigned int i = 0; i < n; i++) {
    for (unsigned int j = 1; j <= N_PROBLEMS; j++) {
      exer[i][I_PER].a += exer[i][j].a;
    }
  }

  my_sum = exer[0][I_PER].a;
  unsigned int deleted = 0;

  // HACK: make first person's score to be zero to not influence the result
  exer[0][I_PER].a = 0;
  // better would be to pop it but popping in front is inefficient in vector.

  // ascending sort of persons based on score
  for (unsigned int i = 0; i < n; i++) {
    std::sort(exer[i].begin() + 1, exer[i].end(), comp_exer1);
  }

  // descending sort of problems for each person
  std::sort(exer.begin(), exer.end(), comp_exer);

  // remove problems with 0 score
  for (unsigned int i = 0; i < n; i++) {
    while (exer[i].back().a == 0) {
      exer[i].pop_back();
    }
  }

  while (exer.back()[I_PER].a > my_sum) {
    deleted += min_count_sum();
    exer.pop_back();
  }

  printf("%u\n", deleted);
  return 0;
}