"""
출처: 프로그래머스 코딩 테스트 연습,
https://school.programmers.co.kr/learn/courses/30/lessons/118668
"""
# 풀이 과정
# 알고력: 0이상의 정수 코딩력: 0이상의 정수
# 조건: 알고력, 코딩력, 알고력 증가량, 코딩력 증가량, 걸리는 시간

# 목표: 모든 문제를 푸는 코딩력,알고력을 얻는 최단 시간 (최단 시간안에 역량 얻기)
# 중요포인트:모든 문제 다 안풀어도 됨,같은 문제 여러번 풀기 가능

# 생각 접근 및 방향 변화: 최대로 걸리는 시간을 산정 후 그 시간에 도달하기 전 코딩력 알고력 체크
# 도달해야 될 알고력과 코딩력을 확인 후 최단 시간에 도달하는 방향으로 나아가는 생각
# 완탐 불가능
# 효율1 알고력 효율2 코딩력을 기준으로 가장 효율이 좋은 것을 넣는 방식 고민
# 시간 대비 효율
# 시간 효율로 dp 구성 가능한지 여부(반복되는 문제를 통해 답을 찾는 과정이라 생각이 들기 때문이다.)
# 요구력에 제일 근사한 값이 두 개 나올 시 dp에 넣을지 생각
# 효율이 떨어져도 검증해야될 필요성 느낌: 문제 푸는데 최소한의 역량 확보와 효율과 차이가 날 수 있음

import heapq

def solution(alp, cop, problems):
    # 목표 역량
    algorism, coding = 0, 0

    for a, c, algo, code, time in problems:
        algorism = max(a, algorism)
        coding = max(c, coding)

    # dp를 활용하기 위한 최대 시간 계산
    if alp >= algorism:
        plus_alp = 0
    else:
        plus_alp = algorism - alp

    if cop >= coding:
        plus_cop = 0
    else:
        plus_cop = coding - cop

    max_time = plus_alp + plus_cop

    if max_time == 0:
        return 0

    dp = [[float("inf")] * (plus_cop + 1) for _ in range(plus_alp + 1)]

    q = [[alp, cop, 0]]

    check = 0

    while q:
        al, co, t = q.pop()

        for a, c, alco, code, time in problems:

            if al >= a and co >= c and (t + time) <= max_time:

                if al + alco >= algorism and co + code >= coding:
                    if dp[plus_alp][plus_cop] > (time + t):
                        dp[plus_alp][plus_cop] = time + t

                elif al + alco >= algorism and co + code < coding:
                    if dp[plus_alp][(co + code) - cop] > (time + t) and time + t < dp[plus_alp][plus_cop]:
                        dp[plus_alp][(co + code) - cop] = time + t
                        q.append([algorism, co + code, time + t])

                elif al + alco < algorism and co + code >= coding and time + t < dp[plus_alp][plus_cop]:
                    if dp[(al + alco) - alp][plus_cop] > (time + t):
                        dp[(al + alco) - alp][plus_cop] = time + t
                        q.append([al + alco, coding, time + t])

                elif al + alco < algorism and co + code < coding and time + t < dp[plus_alp][plus_cop]:
                    if dp[(al + alco) - alp][(co + code) - cop] > (time + t):
                        dp[(al + alco) - alp][(co + code) - cop] = time + t
                        q.append([al + alco, co + code, time + t])

        if (al + 1) <= algorism and t + 1 < dp[plus_alp][plus_cop]:
            if co >= coding:
                if dp[al + 1 - alp][plus_cop] > t + 1:
                    q.append([al + 1, coding, t + 1])
            else:
                if dp[al + 1 - alp][co - cop] > t + 1:
                    dp[al + 1 - alp][co - cop] = t + 1
                    q.append([al + 1, co, t + 1])

        if (co + 1) <= coding and t + 1 < dp[plus_alp][plus_cop]:

            if al >= algorism:
                if dp[plus_alp][co + 1 - cop] > t + 1:
                    q.append([algorism, co + 1, t + 1])
            else:

                if dp[al - alp][co + 1 - cop] > t + 1:
                    dp[al - alp][co + 1 - cop] = t + 1
                    q.append([al, co + 1, t + 1])

    return dp[-1][-1]