게임 팬

이 문제에 언급된 모든 상표와 등록 상표는 각 소유자의 재산이다.

컴퓨터가 발명된 이후로 컴퓨터 게임은 우리 생활에서 컴퓨터의 가장 중요한 응용 중 하나가 되었다. 매혹적인 화면, 사랑스러운 음성, 흡인력 있는 줄거리는 ‘게임 팬’이라 불리는 사람들을 컴퓨터 게임에 깊이 빠져들게 했다. 오늘날 세계에서 가장 앞선 컴퓨터 기술이 컴퓨터 게임에 사용되지만, ‘게임 팬’이 게임에 항상 만족하는 것은 아니며, 특히 가격에 그렇다. 컴퓨터 게임의 화면이 매혹적이고 음성이 사랑스럽고 줄거리가 흡인력 있을수록 가격이 높다. 게다가 ‘게임 팬’은 더 앞선 (더 비싼) 장비를 구매해야 한다.

아시다시피 모든 게임 팬이 큰 재산을 가진 것은 아니다. 컴퓨터 게임의 다양한 하드웨어와 소프트웨어 앞에서, 팬은 그중 일부를 구매하려는 결정을 내리고자 할 때 망설이게 된다. 그러나 안타깝게도 팬은 특정 소프트웨어를 실행하려면 대응하는 하드웨어를 구매해야 한다. 예를 들어, “Mario Bro.”는 Nintendo Incorporation의 소프트웨어 제품 중 하나이며, “Family Computer” (Nintendo Incorporation의 하드웨어 제품 중 하나)를 가진 사람만 실행할 수 있다. 따라서 게임 팬은 “Mario Bro.”를 사고 싶다면 먼저 “Family Computer”를 사야 한다. Nintendo Incorporation의 또 다른 게임인 “Duck Hunter”에 관한 예도 있다. “Duck Hunter”를 실행하려면 게임 팬은 Nintendo Incorporation이 “Family Computer”를 위해 특별히 설계한 “Laser Gun”을 사야 한다. “Family Computer”와 “Duck Hunter”는 있지만 “Laser Gun”이 없는 사람도, “Laser Gun”과 “Duck Hunter”는 있지만 “Family Computer”가 없는 사람도 이 게임을 실행할 수 없다. 그리고 게임 팬이 “Family Computer”를 가지고 있으면 “Family Computer”용으로 설계된 어떤 게임이든 또 다른 “Family Computer”를 구매하지 않고 실행할 수 있다. 예를 들어, “Mario Bro.”와 “Mario Bro. II”는 모두 “Family Computer”용으로 설계되었으므로, “Family Computer”를 가진 사람은 “Mario Bro.”와 “Mario Bro. II”를 마음껏 즐길 수 있다. 마지막으로, 특정 하드웨어와 소프트웨어를 가진 게임 팬은 대응하는 컴퓨터 게임을 충분히 즐겼으므로 같은 하드웨어나 같은 소프트웨어를 다시 사는 것은 의미가 없다. 결국 같은 하드웨어나 같은 소프트웨어는 게임 팬에게 추가적인 즐거움을 주지 않는다.

이 문제에서 당신은 게임 팬에 대한 설명, 즉 그의 현금과 그가 사고 싶어 하는 하드웨어와 소프트웨어의 상세 목록을 받는다. 목록에는 하드웨어와 소프트웨어의 이름, 그것들이 의존하는 장비, 가격, 팬에게 줄 즐거움이 포함된다. 팬의 현금이 제한적이므로 목록의 모든 하드웨어와 소프트웨어를 살 수 없다는 것은 불운이다. 그래서 당신은 그를 돕는 프로그램을 작성해야 한다. 당신의 프로그램은 팬이 얻을 수 있는 최대 즐거움과 그에 해당하는 즐거움을 위해 지불할 현금을 계산해야 한다. 의심할 바 없이, 팬은 그 즐거움을 지불할 능력이 있어야 한다.

• 당신의 프로그램은 상세 목록의 각 항목에 대해 살지 말지 결정해야 하며, 같은 항목을 두 번 이상 사서는 안 된다. 즉, 목록의 각 항목은 최대 한 번만 살 수 있다.
• 목록의 일부 항목을 사지 않으면, 그 항목들은 팬에게 어떤 즐거움도 주지 않는다. 그리고 그 항목들에 의존하는 다른 항목들도 팬에게 어떤 즐거움도 주지 않는다.
• 상세 목록에 순환 의존이 없다고 가정할 수 있다. 예를 들어, 다음과 같은 상황은 일어나지 않는다. 상세 목록에서 항목 A가 항목 B에 의존하고, 항목 B가 항목 C에 의존하고, 항목 C가 항목 A에 의존한다.
• 같은 항목에 의존하는 항목은 목록에 32개 이하라고 가정할 수 있다. 그리고 의존의 깊이는 5 미만이다.

이 문제의 입력은 여러 테스트 케이스로 구성된다. 각 테스트 케이스는 여러 줄을 포함한다. ‘%’ 하나만 있는 줄은 테스트 케이스의 끝을 나타낸다. 각 테스트 케이스의 첫 줄에는 게임 팬의 이름인 ‘word’ (‘word’는 알파벳과 숫자 문자로 구성된 연속 문자열)와 팬의 현금인 정수 m (0 ≤ m ≤ 1024)이 주어진다. 그 뒤에 목록의 항목들이 여러 줄에 걸쳐 주어지며, 각 항목은 별도의 줄에 있다. 각 줄에는 2개의 ‘word’와 2개의 정수가 있다. 첫 번째 ‘word’는 항목의 이름이다. 두 번째 ‘word’는 그 항목 (첫 번째 ‘word’의 항목)이 의존하는 다른 항목이다. 두 번째 ‘word’가 ‘&’이면, 그 항목은 다른 어떤 항목에도 의존하지 않는다. 첫 번째 정수는 항목의 가격인 ci (0 ≤ ci ≤ 1024)이고, 두 번째 정수는 팬이 그 항목에서 얻을 수 있는 즐거움인 hi (0 ≤ hi ≤ 100000)이다. 첫 줄에 ‘#’ 하나만 있는 케이스는 입력 파일의 끝을 나타낸다. 이 케이스는 처리하지 않는다. 입력 파일의 ‘word’는 대소문자를 구분한다. 샘플 입력에는 문제에 대한 완전한 케이스가 포함되어 있다.

각 테스트 케이스의 출력은 게임 팬의 이름을 나타내는 줄로 시작한다. 다음 줄에는 ‘Max happiness:’라는 문자열과 그 케이스에서 팬이 얻을 수 있는 즐거움을 나타내는 정수가 있다. 그 뒤에 ‘Cost:’라는 문자열과 그에 해당하는 즐거움을 위해 팬이 지불해야 하는 현금을 나타내는 정수가 있는 줄이 온다. 최대 즐거움을 얻는 방법이 여러 개면, 그 즐거움을 얻는 최소 비용을 출력한다. 각 케이스 사이에 빈 줄을 출력한다. 출력에 더 이상의 공백 문자를 인쇄해서는 안 된다.