import java.util.Scanner;
import java.io.*;

public class Knapsack {

   private Item[] items;
   private int numItems, capacity;


   public static void main(String[] args) throws FileNotFoundException {
      Knapsack k = new Knapsack();
      k.initialize(); 
      System.out.println("Total Value: " + k.answer(k.numItems-1,k.capacity));
   }


   private void initialize() throws FileNotFoundException {
      int i;
      Scanner input = new Scanner(new File("data.txt"));

      capacity = input.nextInt();
      numItems = input.nextInt();
      items = new Item[numItems];
      for (i=0; i<numItems; i++)
         items[i] = new Item(input.nextInt(),input.nextInt());
   }


   private int answer(int lastAllowed, int cap) {
      int take, dontTake;

      if (lastAllowed < 0)
         return 0;

      take = items[lastAllowed].getValue() + 
             answer(lastAllowed-1,cap-items[lastAllowed].getWeight());

      dontTake = answer(lastAllowed-1,cap);

      if (items[lastAllowed].getWeight() > cap)
         return dontTake;

      return Math.max(take,dontTake);
   }
}



class Item {

   private int value, weight;

   public Item(int v, int w) {
      value = v; weight = w;
   }

   public int getValue() {
      return value;
   }

   public int getWeight() {
      return weight;
   }
}