/* recursive memo

   copyright (c) 2014 by dekaino
   ssasaki@dekaino.net
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NUM 50
#define LINEBUFSZ 1024
#define NOTFOUND 999999999
#undef DEBUG


struct st_bymen {
  int men;
  int num;
  int cost[MAX_NUM];
};

struct st_total {
  int m;
  int n;
  int q[MAX_NUM];
  int r[MAX_NUM];
  int numkind;
  struct st_bymen *bymen[MAX_NUM];
  int *memo_cost[MAX_NUM];
  int *memo_men[MAX_NUM];
#ifdef DEBUG
  int men_total;
  int cost_total;
  int findcounter;
#endif
} total;


void setmemo(struct st_total *tot, 
	     int menmin, int menmax, int level, int cost, int nummen) {
  int start, i;
  int *memo_cost = tot->memo_cost[level];
  int *memo_men = tot->memo_men[level];

#ifdef DEBUG
  printf("setmemo %d %d %d %d %d\n", menmin, menmax, level, cost, nummen);
#endif

  if (menmin < 0) {
    start = 0;
  } else {
    start = menmin;
  }

  for(i=start; i<=menmax; i++){
    if (memo_cost[i] == 0 || memo_cost[i] > cost) {
      memo_cost[i] = cost;
      memo_men[i] = nummen;
    }

    if (memo_cost[i] > cost) {
      printf("setmemo men=%d level=%d memo_cost=%d cost=%d\n",
	     i, level, memo_cost[i], cost);
    }
  }
}

int getmemo(struct st_total *tot, int men, int level, int *nummen) {
  int *memo_cost = tot->memo_cost[level];
  int *memo_men = tot->memo_men[level];

#ifdef DEBUG
  printf("getmemo %d %d ", men, level);
#endif

  if (memo_cost[men] == 0) {
#ifdef DEBUG
    puts("");
#endif
    return 0;
  }
  *nummen = memo_men[men];
#ifdef DEBUG
  printf("cost=%d, men=%d\n", memo_cost[men], memo_men[men]);
#endif
  return memo_cost[men];
}

void findout(struct st_total *tot, int level, int men, int cost,
	     int *plastmen, int *plastcost) {
  int orgmen = men;
  int orgcost = cost;
  int num = tot->bymen[level]->num;
  int bym_men = tot->bymen[level]->men;
  int *bym_cost = tot->bymen[level]->cost;
  int i, j;
  int lastmen, lastcost;
  int partcost[MAX_NUM+1], partmen[MAX_NUM+1];
  int mincost, minmen;
  
#ifdef DEBUG
  tot->findcounter++;
#endif

  /* 1st: not adopt this level */
  if (level+1 < tot->numkind) {
    /* check cached data */
    lastcost = getmemo(tot, men, level+1, &lastmen);
    if (lastcost==0) {
      /* no cached data causes calling findout() */
      findout(tot, level+1, men, cost, &lastmen, &lastcost);
    } else if (lastcost != NOTFOUND) {
      lastmen += men;
      lastcost += cost;
    }
    partmen[0] = lastmen;
    partcost[0] = lastcost;
  } else {
    partmen[0] = NOTFOUND;
    partcost[0] = NOTFOUND;
  }

  /* 2nd: adopt this level */
  for (i=0; i<num; i++) {
    men += bym_men;
    cost += bym_cost[i];

    if (men >= tot->m) {
      /* earn enough man power */
#ifdef DEBUG
      if (tot->men_total < 0 || cost < tot->cost_total) {
	/* find better answer than all known answers */
	tot->men_total = men;
	tot->cost_total = cost;
      }
#endif
      partmen[i+1] = men;
      partcost[i+1] = cost;
      i++;
      break;
    } else if (level+1 < tot->numkind) {
      /* not enough man power */
      /* check cached data */
      lastcost = getmemo(tot, men, level+1, &lastmen);
      if (lastcost==0) {
	/* no cached data causes calling findout() */
	findout(tot, level+1, men, cost, &lastmen, &lastcost);
      } else if (lastcost != NOTFOUND) {
	lastmen += men;
	lastcost += cost;
      }
      partmen[i+1] = lastmen;
      partcost[i+1] = lastcost;
    } else {
      partmen[i+1] = NOTFOUND;
      partcost[i+1] = NOTFOUND;
    }
  }

  /* find partial best cost */
  lastmen = partmen[0];
  mincost = partcost[0];
  for(j=1; j<i+1; j++) {
    if (mincost > partcost[j]) {
      lastmen = partmen[j];
      mincost = partcost[j];
    }
  }

  minmen = (lastmen == NOTFOUND) ? orgmen : orgmen - lastmen + tot->m;
  setmemo(tot, minmen, orgmen, level, 
	  (mincost == NOTFOUND) ? NOTFOUND : mincost - orgcost,
	  (lastmen == NOTFOUND) ? NOTFOUND : lastmen - orgmen);

  *plastmen = lastmen;
  *plastcost = mincost;
}


/* st_total compare function */
int comp_bymen( const void *c1, const void *c2 )
{
  struct st_bymen *p1 = *(struct st_bymen **)c1;
  struct st_bymen *p2 = *(struct st_bymen **)c2;
  int tmp1 = p1->men;
  int tmp2 = p2->men;

  if( tmp1 < tmp2 )  return -1;
  if( tmp1 == tmp2 ) return  0;
  /*  if( tmp1 > tmp2 )  return  1; */
  return 1;
}


/* integer compare function */
int comp( const void *c1, const void *c2 )
{
  int tmp1 = *(int *)c1;
  int tmp2 = *(int *)c2;

  if( tmp1 < tmp2 )  return -1;
  if( tmp1 == tmp2 ) return  0;
  /*  if( tmp1 > tmp2 )  return  1; */
  return 1;
}


int main(void) {
  char buf[LINEBUFSZ];
  int i, j, next;
  int lastmen, lastcost;

  /* STEP 0: intialize */
  total.m = 0;
  total.n = 0;
#ifdef DEBUG
  total.men_total = -1;
  total.cost_total = -1;
  total.findcounter = 0;
#endif
  for (i=0; i<MAX_NUM; i++) {
    total.bymen[i] = malloc(sizeof (struct st_bymen));
    if (!total.bymen[i]) {
      fputs("malloc() error\n", stderr);
      return 1;
    }
  }

  /* STEP 2: parse input parameter */
  if (!fgets(buf, LINEBUFSZ, stdin)) {
    fputs("cannot get m\n", stderr);
    return 1;
  }
  total.m = atoi(buf);
  if (total.m<1 || total.m>200000) {
    fprintf(stderr, "Bad m=%d\n", total.m);
    return 1;
  }

  if (!fgets(buf, LINEBUFSZ, stdin)) {
    fputs("cannot get n\n", stderr);
    return 1;
  }
  total.n = atoi(buf);
  if (total.n<1 || total.n>50) {
    fprintf(stderr, "Bad n=%d\n", total.n);
    return 1;
  }

  for (i=0, next=0; i<total.n; i++) {
    char *pcq, *pcr;
    int iq, ir;

    if (!fgets(buf, LINEBUFSZ, stdin)) {
      fprintf(stderr, "cannot get q[%d], r[%d]\n", i);
      return 1;
    }

    pcq = strtok(buf, " \t");
    pcr = strtok(NULL, " \t");
    if (!pcq || !pcr) {
      fprintf(stderr, "cannot get q[%d], r[%d]\n", i);
      return 1;
    }

    iq = atoi(pcq);
    ir = atoi(pcr);
    if (iq<1 || iq>10000 || ir<1 || ir>5000000) {
      fprintf(stderr, "Bad q[%d]=%d, r[%d]=%d\n", i, iq, i, ir);
      return 1;
    }
    total.q[i] = iq;
    total.r[i] = ir;

    /* search for same number_of_men company */
    for (j=0; j<next; j++) {
      if (total.bymen[j]->men == iq) break;
    }
    if (j==next) {
      /* create new record because of not found */
      total.bymen[j]->men = iq;
      total.bymen[j]->cost[0] = ir;
      total.bymen[j]->num = 1;
      next++;
    } else {
      /* register to record of same number */
      total.bymen[j]->cost[total.bymen[j]->num++] = ir;
    }
  }

  /* STEP 3: sort parameter */
  total.numkind = next;
  qsort(total.bymen, next, sizeof (struct st_bymen*), comp_bymen);
  for (i=0; i<next; i++) {
    if (total.bymen[i]->num > 1) {
      /* quick sort */
      qsort(total.bymen[i]->cost, total.bymen[i]->num, sizeof (int), comp);
    }
  }

  /* STEP 4: prepare memo arrays */
  for (i=0; i<next; i++) {
    total.memo_cost[i] = malloc(sizeof(int) * total.m);
    if (!total.memo_cost[i]) {
      fputs("malloc() error\n", stderr);
      return 1;
    }
    memset(total.memo_cost[i], 0, sizeof(int) * total.m);
    total.memo_men[i] = malloc(sizeof(int) * total.m);
    if (!total.memo_men[i]) {
      fputs("malloc() error\n", stderr);
      return 1;
    }
    memset(total.memo_men[i], 0, sizeof(int) * total.m);
  }

  /* STEP 5: find out best answer */
  findout(&total, 0, 0, 0, &lastmen, &lastcost);

  /* STEP 6: output best answer */
#ifdef DEBUG
  printf("m=%d, n=%d\n", total.m, total.n);
  for (i=0; i<total.n; i++) {
    printf("q[%d]=%d, r[%d]=%d\n", i, total.q[i], i, total.r[i]);
  }
  for (i=0; i<total.numkind; i++) {
    printf("men[%d]=%d, num[%d]=%d",
	   i, total.bymen[i]->men, i, total.bymen[i]->num);
    for (j=0; j<total.bymen[i]->num; j++) {
      printf(" / %d",total.bymen[i]->cost[j]);
    }
    puts("");
  }

  printf("men_total=%d, cost_total=%d, findcounter=%d\n",
	 total.men_total, total.cost_total, total.findcounter);
  printf("last_men=%d, last_cost=%d\n", lastmen, lastcost);
#endif

  printf("%d\n", lastcost);
  return 0;
}