from heapq import heappush, heappop

def get_bound(u_level, u_weight, u_profit, n, capacity, items):
    if u_weight >= capacity:
        return 0
    
    bound = u_profit
    j = u_level + 1
    tot_weight = u_weight
    
    while j < n and tot_weight + items[j][1] <= capacity:
        tot_weight += items[j][1]
        bound += items[j][0]
        j += 1
        
    if j < n:
        bound += (capacity - tot_weight) * (items[j][0] / items[j][1])
        
    return bound

def solve():
    try:
        # Read capacity and number of items
        first_line = input().split()
        if not first_line:
            return
        capacity = int(first_line[0])
        
        second_line = input().split()
        if not second_line:
            return
        n = int(second_line[0])
        
        raw_items = []
        for _ in range(n):
            # Reading p, w, and priority
            item_data = input().split()
            if not item_data:
                break
            p = int(item_data[0])
            w = int(item_data[1])
            # Priority is read but not used as per the problem hint
            raw_items.append((p, w))
            
    except EOFError:
        pass

    # Sort by profit/weight ratio descending
    items = sorted(raw_items, key=lambda x: x[0]/x[1], reverse=True)

    # Priority Queue stores tuples: (-upper_bound, level, current_profit, current_weight)
    pq = []
    
    max_profit = 0
    root_bound = get_bound(-1, 0, 0, n, capacity, items)
    heappush(pq, (-root_bound, -1, 0, 0))

    while pq:
        bound, level, profit, weight = heappop(pq)
        bound = -bound
        
        if bound <= max_profit:
            continue
            
        next_level = level + 1
        
        # Branch 1: Include the item
        if next_level < n:
            in_weight = weight + items[next_level][1]
            in_profit = profit + items[next_level][0]
            
            if in_weight <= capacity:
                if in_profit > max_profit:
                    max_profit = in_profit
                
                in_bound = get_bound(next_level, in_weight, in_profit, n, capacity, items)
                if in_bound > max_profit:
                    heappush(pq, (-in_bound, next_level, in_profit, in_weight))
                    
        # Branch 2: Exclude the item
        if next_level < n:
            ex_weight = weight
            ex_profit = profit
            
            ex_bound = get_bound(next_level, ex_weight, ex_profit, n, capacity, items)
            if ex_bound > max_profit:
                heappush(pq, (-ex_bound, next_level, ex_profit, ex_weight))

    print(f"Maximum Profit: {max_profit}")

if __name__ == "__main__":
    solve()

# Sample Test Case
# ----------------
# Input:
# 15
# 4
# 10 2 1
# 10 4 2
# 12 6 3
# 18 9 4
#
# Output:
# Maximum Profit: 38
#
# Explanation:
# Capacity = 15
# Items (Profit, Weight, Priority):
# 1. (10, 2)
# 2. (10, 4)
# 3. (12, 6)
# 4. (18, 9)
# Optimal selection: Items 1, 2, 4 -> Weights: 2+4+9=15, Profit: 10+10+18=38.