Amar and asha play spaceking

import sys
sys.setrecursionlimit(10000)

def max_gold(index, aliens_hp, turn, memo):
    key = (index, tuple(aliens_hp), turn)
    if key in memo:
        return memo[key]
    
    n = len(aliens_hp)
    
    # If all aliens are dead
    if all(hp <= 0 for hp in aliens_hp):
        return 0
    
    if turn == 0:  # Asha's turn
        max_gain = 0
        for i in range(n):
            if aliens_hp[i] <= 0:
                continue
            new_hp = aliens_hp[:]
            new_hp[i] -= P
            gain = 0
            if new_hp[i] <= 0:
                gain = G[i]
            max_gain = max(max_gain, gain + max_gold(index, new_hp, 1, memo))
        # Asha can also choose to skip
        max_gain = max(max_gain, max_gold(index, aliens_hp, 1, memo))
        memo[key] = max_gain
        return max_gain
    else:  # Amar's turn
        new_hp = aliens_hp[:]
        # find the closest alive alien
        for i in range(n):
            if new_hp[i] > 0:
                new_hp[i] -= Q
                break
        result = max_gold(index, new_hp, 0, memo)
        memo[key] = result
        return result


# Read input
P, Q, N = map(int, input().split())
H = []
G = []
for _ in range(N):
    hi, gi = map(int, input().split())
    H.append(hi)
    G.append(gi)

memo = dict()
result = max_gold(0, H, 0, memo)
print(result)