MVP 다이아몬드 (Normal)

입력 제한 외에 난이도에 따른 문제의 차이는 없다.

상민이는 게임 단풍잎이야기에 과금을 즐겨 한다. 단풍잎이야기에는 과금액에 따라 혜택을 제공하는 'MVP 등급'이 있다.

MVP 등급은 브론즈(B), 실버(S), 골드(G), 플래티넘(P), 다이아몬드(D)로 다섯 등급이 있으며, 현재 달과 지난달, 즉 현재 달을 포함한 최근 2개월간의 과금액으로 결정된다.

단, 단풍잎이야기에는 과도한 과금을 막기 위해 '최대 과금 한도'가 있어 한 달에 최대 다이아몬드 등급 기준액까지 과금할 수 있으며, 만원 단위로만 과금할 수 있다.

MVP 등급은 해당 달이 끝날 때 계산되어 책정된다. 예를 들어 아래 표와 같은 등급 기준액을 따르고 1월에 게임을 시작한 상민이가 1월에 30만, 2월에 20만, 3월에 50만 원을 과금했다면 1월(30만)과 2월(30+20=50만)에는 실버 등급, 3월(20+50=70만)에는 골드 등급으로 책정된다.

<표1> 위 예시의 등급 기준표

상민이는 게임을 시작하고 N개월 동안 수많은 현금을 과금해왔다. 상민이는 이 사실을 자신의 여자친구에게만은 철저히 비밀로 하고 있었다. 상민이의 여자친구는 상민이가 게임에 과금하는 것을 매우 싫어했기 때문이다. 그러던 어느 날 문제가 발생했다. 상민이의 여자친구에게 N개월간의 MVP 등급 기록이 유출된 것이다!

상민이의 여자친구는 상민의 과금액을 역추적하기 위해 당신에게 부탁했다.

상민이의 여자친구: 상민이가 게임에 최대 얼마나 과금한건지 알려줘.

둘 사이에 어떤 일이 벌어질지는 모르겠지만, 당신은 상민이의 여자친구를 위한 프로그램을 작성해야만 한다.

첫 번째 줄에는 게임을 플레이 한 개월수 N이 주어진다.

두 번째 줄에는 실버, 골드, 플래티넘, 다이아몬드 등급 기준액 s, g, p, d가 만원 단위로 순서대로 주어진다. 브론즈 등급 기준액은 0 원이다.

세 번째 줄에는 게임을 플레이 한 첫 번째 달부터 N번째 달까지의 MVP 등급이 등급 표기대로 주어진다. 기록과 같은 MVP 등급 달성이 불가능한 경우는 주어지지 않는다.

입력된 MVP 등급을 달성하기 위한 최대 누적 과금액을 만원 단위로 출력한다.

1 ≤ N ≤ 36

0 < s < g < p < d ≤ 500