#include <stdio.h>
#include <stdlib.h>
/* testni program, da vidim, če razumem nalogo */
struct voznik {
int t;
int v;
};
int najdi (int ** sp, int n, int * prijatelji, int * po, int prij) {
int s = 0;
/* preverimo, če smo našli */
for (int i = 0; i < prij; i++) {
if (po[i])
continue;
s++;
for (int j = 0; j < prij; j++) {
if (po[i])
continue;
if (i == j)
continue;
if (!sp[prijatelji[i]][prijatelji[j]] && !sp[prijatelji[j]][prijatelji[i]])
goto n;
}
}
return s;
n:
s = -1;
for (int i = 0; i < prij; i++) {
if (po[i]) /* je bil odstranjen */
continue;
po[i]++;
int ns = najdi(sp, n, prijatelji, po, prij);
po[i]--;
if (ns > s)
s = ns;
}
return s;
}
int spop (int l, struct voznik * i, struct voznik * j) {
return (i->t < j->t && l/i->v+i->t > l/j->v+j->t);
}
int primerjaj_voznike (const void * a, const void * b) {
const struct voznik * c = (const struct voznik *) a;
const struct voznik * d = (const struct voznik *) b;
return c->t - d->t;
}
int main (int argc, char ** argv) {
int l, n, i, s, ** sp, * prijatelji, * po;
char * c, * buf;
struct voznik * vozniki;
buf = malloc(500);
fgets(buf, 500, stdin);
l = strtol(buf, &c, 10);
c++;
n = strtol(c, NULL, 10);
vozniki = calloc(n, sizeof(struct voznik));
sp = calloc(n, sizeof(int *));
prijatelji = calloc(n, sizeof(int));
po = calloc(n, sizeof(int));
for (int i = 0; i < n; i++)
sp[i] = calloc(n, sizeof(int)); /* alloc bi lahko zgolj (n-i)-1 ampak ok */
i = 0;
while (i < n) {
fgets(buf, 500, stdin);
vozniki[i].t = strtol(buf, &c, 10);
c++;
vozniki[i++].v = strtol(c, NULL, 10);
}
qsort(vozniki, n, sizeof(struct voznik), primerjaj_voznike);
for (int i = 0; i < n-1; i++)
for (int j = i+1; j < n; j++)
if (spop(l, vozniki+i, vozniki+j) && !sp[i][j])
sp[i][j]++;
/* debug, tabelica */
for (int i = 0; i < n; i++) {
fprintf(stderr, "%d:", i);
for (int j = 0; j < n; j++)
fprintf(stderr, " %d", sp[i][j]);
fprintf(stderr, "\n");
}
s = 0;
/* sedaj gremo po voznikih in najdemo osebo z največ skupinskimi prijatelji */
for (int v = 0; v < n; v++) {
int sest = 0;
int prij = 1;
prijatelji[0] = v;
/* po vrstici */
for (int j = v+1; j < n; j++)
if (sp[v][j])
prijatelji[prij++] = j;
/* po stolpcu */
for (int i = 0; i < v; i++)
if (sp[i][v])
prijatelji[prij++] = i;
/* rekurzivno odstranjujemo prijatelje dokler ne najdemo najbolj optimalne skupine */
sest = najdi(sp, n, prijatelji, po, prij);
if (sest > s)
s = sest;
}
for (int i = 0; i < n; i++)
free(sp[i]);
free(buf);
free(vozniki);
free(sp);
fprintf(stdout, "%d\n", s);
return 0;
}
