아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

마법 슬레이어

시간 제한8초메모리 제한512 MB

요약
각각 체력을 가진 N마리 몬스터와 한 마리 또는 전체를 공격하는 M개의 주문이 주어질 때, 모든 몬스터를 처치하는 최소 마력 소모를 구한다.
난이도

어려움10점 중 8점

유형
동적 계획법, 그리디, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

몬스터가 넘치는 판타지 세계에서, 당신은 마법으로 몬스터와 싸우는 슬레이어다.

각 몬스터는 생명력을 나타내는 체력을 가진다. 마법으로 체력을 줄일 수 있다. 각 마법은 일정량의 피해를 주어 몬스터의 체력을 감소시키며, 그 대상은 마법에 따라 몬스터 하나이거나 눈앞의 모든 몬스터이다. 몬스터는 체력이 0 이하가 되면 쓰러진다. 한편 각 마법은 일정량의 마력을 소모할 수 있다. 마력은 한정되어 있으므로, 최소한의 마력으로 몬스터를 쓰러뜨리려 한다.

이를 위한 프로그램을 작성하시오.

입력

입력은 여러 개의 데이터셋으로 이루어진다. 각 데이터셋은 다음 형식이다.

N
HP1
HP2
...
HPN
M
Name1 MP1 Target1 Damage1
Name2 MP2 Target2 Damage2
...
NameM MPM TargetM DamageM

N은 눈앞에 있는 몬스터의 수(1 ≤ N ≤ 100)이다. HPi는 i번째 몬스터의 체력(1 ≤ HPi ≤ 100000)이다. M은 사용할 수 있는 마법의 수(1 ≤ M ≤ 100)이다. Namej는 j번째 마법의 이름으로, 최대 16자의 영문 대소문자로 이루어진다. MPj는 j번째 마법이 소모하는 마력(0 ≤ MPj ≤ 99)이다. Targetj는 "Single" 또는 "All"이며, 각각 j번째 마법이 몬스터 하나에게만 피해를 주는지 모든 몬스터에게 피해를 주는지를 나타낸다. Damagej는 j번째 마법이 주는 피해량("All"인 경우 몬스터마다)이다(0 ≤ Damagej ≤ 999999).

입력의 모든 수는 정수이다. 몬스터에게 0이 아닌 피해를 주는 마법이 적어도 하나 있다.

마지막 데이터셋 다음에는 0 하나가 있는 줄이 온다. 이 줄은 어떤 데이터셋에도 속하지 않으며 처리하지 않는다.

출력

각 데이터셋에 대해, 입력의 모든 몬스터를 쓰러뜨리는 데 소모되는 최소 마력을 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    3
8000 15000 30000
3
Flare 45 Single 8000
Meteor 62 All 6000
Ultimate 80 All 9999
0
    예상 출력
    232