카트 제작

다오는 카트라이더 게임을 즐겨한다. 카트라이더를 더욱 재미있게 즐기기 위해서 보유하고 있는 파츠들을 조합하여 카트를 구성하려고 한다.

파츠 종류는 다음과 같이 다섯 가지가 있다.

• 카트바디 (Body)
• 핸들 (Handle)
• 바퀴 (Wheel)
• 엔진 (Engine)
• 부스터 (Booster)

다오는 각 파츠 종류마다 다양한 파츠들을 가지고 있다. 각 파츠는 고유의 이름과 파츠의 정해진 성능이 있다. 다오는 각 파츠 종류마다 한 개의 파츠를 선택해서 조합하여 카트를 만들 수 있다.

어떤 파츠들은 같이 조합될 경우 시너지 효과가 있고, 이 시너지 효과는 카트의 전체 성능을 증가시킨다.

위 그림은 다섯 종류의 파츠 사이에 시너지 효과가 있을 수 있는 종류 관계를 보여 주고 있다. 양방향 화살표로 된 파츠 종류 사이엔 시너지 효과가 있을 수 있다. 즉, 카트바디는 다른 네 종류의 파츠와 모두 시너지 효과가 있을 수 있고, 엔진과 부스터 사이와 핸들과 바퀴 사이에도 시너지 효과가 있을 수 있다.

다오는 주어지는 $S$에 최대한 가까운 성능을 가지는 카트를 만들고 싶다. $S$에 최대한 가까운 성능을 가진다는 것은 다오가 만든 카트의 성능과 $S$의 차이가 가장 작은 것을 의미한다.

카트의 성능이란, 선택된 파츠의 성능의 합과 시너지가 있는 파츠들을 같이 조합할 때 발생되는 시너지 효과의 합을 더한 것을 의미한다.

다오를 도와, 주어지는 $S$에 최대한 가까운 성능을 가지는 카트를 만드는 프로그램을 작성하시오.

입력 형식

첫 줄에 사용 가능한 파츠의 개수를 나타내는 정수 $N$이 주어진다. $(5 \le N \le 600)$

이어지는 $N$ 개 줄의 $i$ 번째 줄에는 $i$ 번째 파츠의 종류를 나타내는 문자열 $t_i$, $i$ 번째 파츠의 이름을 나타내는 문자열 $m_i$, $i$ 번째 파츠의 성능을 나타내는 정수 $s_i$가 공백으로 구분되어 주어진다. ($1 \le s_i \le 100\,000\,000\,000\,000\,000$)

여기서, $t_i$는 Body, Handle, Wheel, Engine, Booster 중 하나이고, $m_i$는 길이가 최대 $10$이며 알파벳 소문자로 되어있다. 각 파츠의 이름은 서로 다르다. 그리고 모든 파츠 종류에 대해 적어도 한 개의 파츠가 주어진다.

그 다음 줄에 시너지 효과가 있는 파츠 관계의 수를 나타내는 정수 $M$이 주어진다. $(0 \le M \le 100\,000)$

이어지는 $M$ 개의 줄에는 시너지 효과의 정보가 주어진다. 각 줄에 파츠 $a$의 이름, 파츠 $b$의 이름, 시너지 효과를 나타내는 정수 $w$가 공백으로 구분되어 주어진다. ($1 \le w \le 100\,000\,000\,000\,000\,000$)

이는 파츠 $a$와 파츠 $b$가 같이 조합될 경우 시너지 효과가 있어 카트의 성능을 $w$ 만큼 증가시킨다는 것을 의미한다. 이때, 존재하지 않은 파츠의 이름은 주어지지 않고, 파츠 $a$의 종류와 파츠 $b$의 종류가 시너지 효과가 없는 종류 관계인 입력은 주어지지 않는다. 예를 들어, 엔진과 핸들 사이에는 시너지 효과가 없으므로 이러한 입력은 주어지지 않는다.

그 다음 줄에 다오가 만들고 싶어하는 카트의 성능을 나타내는 정수 $S$가 주어진다. ($1 \le S \le 1\,000\,000\,000\,000\,000\,000$)

출력 형식

$S$에 최대한 가까운 성능을 가지는 카트를 조합하여 만들 때 사용하는 카트바디, 핸들, 바퀴, 엔진, 부스터의 파츠 이름을 각 줄에 순서대로 출력한다. 만약, 답이 여러 가지인 경우 그중 아무거나 하나 출력한다.

예제

9
Body red 50
Body purple 50
Handle redsoft 30
Handle redhard 40
Handle purplesoft 30
Wheel purplehard 50
Engine redstrong 20
Engine purplecalm 10
Booster redcalm 10
5
red redsoft 20
red redhard 20
purplesoft purplehard 100
redstrong red 10
redstrong redcalm 50
169

red
redsoft
purplehard
purplecalm
redcalm

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설