반응
시간 제한8초메모리 제한512 MB
색깔별 양의 구슬과 음의 구슬 개수, 그리고 반응 목록이 주어질 때, 서로 겹치지 않는 반응 쌍을 골라 아이템 판매 금액의 합이 최대가 되도록 한다.
문제
당신은 역할 수행 게임의 주인공이다. 왕은 사람들의 목숨을 위협하는 몬스터를 물리쳐 달라고 당신에게 부탁했다.
동료들과 함께 오랜 여정을 거쳐, 당신은 몬스터의 우두머리가 사는 최종 던전에 가장 가까운 마을에 도착했다. 사람들에게 들은 바로는 우두머리 몬스터는 강한 팔로 공격하고, 강력한 주문을 외우며, 여러 특수 능력을 지니고 있다고 한다. 강력한 장비가 없으면 심한 피해를 입어 일행이 쉽게 전멸할 것이다. 따라서 장비를 준비해야 한다.
한편, 여정 중에 모은 마법 구슬이 여러 개 있다. 구슬 자체는 쓸모가 없지만, 반응 주문을 걸면 특별한 아이템으로 바꿀 수 있다. 그 특별한 아이템을 마을의 상점에 팔아 돈을 얻고, 그 돈으로 장비를 살 수 있다.
반응 주문은 다음과 같이 작동한다. 각 구슬에는 색과, 양의 속성 또는 음의 속성 중 하나가 있다. 양의 속성 구슬 하나와 음의 속성 구슬 하나를 골라 두 구슬에 주문을 건다. 그러면 두 구슬이 반응하여 특별한 아이템 한 묶음이 생긴다. 반응이 끝난 구슬은 사라진다. 얻게 되는 아이템 묶음은 오직 두 구슬의 색에만 달려 있다. 주문은 원하는 만큼 걸 수 있지만, 이미 사라진 구슬에는 주문을 걸 수 없다. 또한 모든 색 쌍이 반응을 일으키는 것은 아니다.
돈을 최대한 많이 얻고 싶은 것은 당연하다. 따라서 주문을 걸기 전에 구슬 쌍을 신중히 골라야 한다. 한편 당신은 뛰어난 프로그래머이므로, 컴퓨터로 최선의 방법을 찾는 프로그램을 작성하는 것은 쉬운 일일 것이다.
이제 할 일은 분명하다. 프로그램을 작성하고 우두머리 몬스터와의 싸움을 준비하자!
입력
입력은 여러 데이터셋으로 이루어진다. 각 데이터셋은 다음과 같은 형식이다.
N- N+
Number of available spheres
Definition of items
Definition of reactions
첫 줄에는 음의 속성 구슬의 서로 다른 색 수 N-와 양의 속성 구슬의 서로 다른 색 수 N+가 주어진다. 데이터셋의 나머지 부분은 세 부분으로 나뉜다.
첫 번째 부분은 가지고 있는 구슬의 수를 설명한다. 이 부분의 형식은 다음과 같다.
K1- K2- ... KN--
K1+ K2+ ... KN++
K**i-는 음의 속성 i번째 색 구슬의 수이고, K**i+는 양의 속성 i번째 색 구슬의 수이다.
두 번째 부분은 아이템의 정의를 담고 있다. 이 부분의 형식은 다음과 같다.
M
A1 P1
...
AM PM
M은 만들 수 있는 아이템의 수이다. 이어지는 M개 줄 각각에는 문자열 Ai와 정수 Pi가 주어지며, 각각 i번째 아이템의 이름과 판매 가격이다.
마지막 부분은 반응의 세부 사항을 제공한다. 이 부분의 형식은 다음과 같다.
L
I1- I1+ NJ1 J1,1 ... J1,NJ1
...
IL- IL+ NJL JL,1 ... JL,NJL
첫 줄에는 반응을 일으킬 수 있는 구슬 색 쌍의 수 L이 주어진다. 이어지는 L개 줄 각각은 두 정수 I**i-와 Ii+로 시작하며, 각각 음의 구슬과 양의 구슬의 색을 나타낸다. 다음 정수 NJi는 구슬 I**i-와 I**i+의 반응으로 생기는 아이템의 수이다. 그 뒤에는 NJi개의 문자열이 이어지며, 각각 아이템 이름이다.
다음을 가정할 수 있다: 1 ≤ N-, N+ ≤ 100; 1 ≤ K**i-, K**i+ ≤ 100; 1 ≤ M ≤ 100; 1 ≤ Pi ≤ 100; 1 ≤ L ≤ 100; 1 ≤ NJi ≤ 10. 또한 아이템 이름은 영숫자로만 이루어지고 길이는 10을 넘지 않는다.
입력의 끝은 두 개의 0이 있는 줄로 나타낸다. 이 줄은 어떤 데이터셋에도 속하지 않는다.
출력
각 데이터셋마다 얻을 수 있는 최대 총 판매 가격을 한 줄에 출력한다.