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

# 풀이 과정
def solution(fees, records):
    # records:시각 차량 번호 내역
    # fees:주차 요금

    result = []  # 차량 번호가 작은거부터 요금 정산
    max_time = 23 * 60 + 59  # 최대 시간
    from collections import deque

    car_in = []  # 입차
    car_out = []  # 출차

    for a in records:
        k = a.split(" ")
        b = k[0].split(":")
        c = int(b[0]) * 60 + int(b[1])

        if k[2] == "IN":
            car_in.append([int(k[1]), int(c)])

        elif k[2] == "OUT":
            car_out.append([int(k[1]), int(c)])

    car_in.sort(key=lambda x: (x[0], x[1]))
    car_out.sort(key=lambda x: (x[0], x[1]))

    car_in = deque(car_in)

    car_num = set([car_in[k][0] for k in range(len(car_in))])

    car_num_check = {}  # 차량 번호별 누적 시간 check
    for t in car_num:
        car_num_check[t] = 0

    # 차량별 주차 시간 누적 계산
    while car_in:
        v, w = car_in.popleft()

        if len(car_out) > 0:
            if car_out[0][0] == v:
                car_num_check[v] += car_out[0][1] - w
                del car_out[0]
            else:
                car_num_check[v] += max_time - w
        else:
            car_num_check[v] += max_time - w

    # print(car_num_check)

    car_num_check = sorted(car_num_check.items(), key=lambda item: item[0])

    # print(car_num_check)

    for a, b in car_num_check:
        if b <= fees[0]:
            result.append(fees[1])
        else:
            if (b - fees[0]) % fees[2] == 0:
                result.append(fees[1] + int((b - fees[0]) / fees[2]) * fees[3])
            else:
                result.append(fees[1] + (int((b - fees[0]) / fees[2]) + 1) * fees[3])

    return result