"""
출처:프로그래머스,
https://school.programmers.co.kr/learn/courses/30/lessons/389480
"""

from collections import deque

def solution(info, n, m):
    q=deque( [ [0,0] ] )    
    
    check=deque(info)
    visited = set([(0,0)])
    
    result=[]
    
    while check:
        # 감당해야할 리스크
        da,db=check.popleft()
        
        # 리스크를 감당했을 때의 위험도 담는 곳
        new_q=deque([])
        
        while q:
            a,b=q.popleft()
            
            if a>=n or b>=m:
                continue
            
            elif a<n and b>=m: 
                new_q.append((a+da,b))
            
            elif a>=n and b<m:
                new_q.append((a,b+db))

            else:
                new_q.append((a+da,b))
                new_q.append((a,b+db))
                
        
        if len(new_q)==0:
            return -1
        
        if len(check)==0:
            result=deque(set(new_q))
        
        else:
            q=q+deque(set(new_q))
    final=[]
    
    for last_a,last_b in result:
        if last_a < n and last_b <m:
            final.append(last_a)
    
    return -1 if len(final) == 0 else min(final)