상인의 모험
시간 제한2초메모리 제한512 MB
격자 위 최대 7개 도시와 무게·가격이 정해진 상품, 무게 한도 W, 시간 한도 T가 주어질 때 시장과 도시를 오가며 얻을 수 있는 최대 이익을 구한다.
문제
ICPC에서 좋은 성적을 내려면 수행이 필수다. 토끼는 ICPC에서 이기고 싶어서 오늘도 수행을 하기로 했다.
오늘의 수행은 도시를 뛰어다니며 교역을 해서 상업의 힘을 손에 넣는 것이다.
앞으로의 수행을 위해서도 가능한 한 많은 자금을 벌고 싶다.
이 세계는 동서남북 방향의 도로가 같은 간격으로 늘어서 바둑판 모양을 이루고 있다. 유일하게 존재하는 시장의 위치를 (0, 0)이라 하고, 도시에는 x 좌표와 y 좌표가 정해져 있다 (좌표가 정수인 점이 교차로에 대응한다). 토끼는 도로를 따라서만 이동할 수 있고, 인접한 교차로 사이를 이동하는 데 1분이 걸린다. 몇몇 교차로에는 도시가 있다. 교역에서는 도시에서 상품을 사서 시장에서 팔아 가격 차이만큼 이익을 얻는다.
토끼의 초기 자금은 충분해서 돈이 부족해 상품을 살 수 없는 일은 없다. 하지만 상품마다 무게가 있고, 토끼는 무게의 합이 W 이하인 상품만 동시에 들고 다닐 수 있다. 따라서 도시에 상품을 사러 갔다가 시장으로 돌아오기를 반복하게 된다. 경우에 따라서는 여러 도시에서 상품을 산 뒤 시장으로 돌아올 수도 있다.
도시에서의 상품 구매와 시장에서의 상품 판매는 즉시 이루어진다고 한다. 또한 도시에 있는 상품이 품절되는 일은 없고, 무한히 살 수 있다.
토끼는 이번에 사고팔 각 상품의 이름, 1개당 무게와 판매 가격, 그리고 각 도시의 x 좌표, y 좌표와 판매 상품의 이름과 가격을 데이터로 정리했다. 토끼는 지금 시장이 있는 (0, 0) 위치에 있다. 프로그램을 써서 제한 시간 T분 동안 얼마나 벌 수 있는지 알아보려 한다.
입력
N M W T
S1 V1 P1
...
SM VM PM
L1 X1 Y1
R1,1 Q1,1
...
R1,L1 Q1,L1
...
LN XN YN
RN,1 QN,1
...
RN,LN QN,LN
N은 도시의 수, M은 상품의 종류 수이다. S**i, V**i, P**i (1 ≤ i ≤ M)는 각각 i번째 상품의 이름, 1개당 무게, 1개당 판매 가격이다. 도시는 1 이상 N 이하의 정수로 나타낸다. L**j, X**j, Y**j (1 ≤ j ≤ N)는 각각 도시 j에서 팔리는 상품의 종류 수, 도시 j의 x 좌표, y 좌표이다. R**j,k, Q**j,k (1 ≤ j ≤ N, 1 ≤ k ≤ L**j)는 각각 도시 j에서 팔리는 k번째 상품의 이름, 가격이다.
1 ≤ N ≤ 7, 1 ≤ M ≤ 7, 1 ≤ W ≤ 10,000, 1 ≤ T ≤ 10,000, 1 ≤ V**i ≤ W, 1 ≤ P**i ≤ 10,000, 1 ≤ L**j ≤ M, -10,000 ≤ X**j ≤ 10,000, -10,000 ≤ Y**j ≤ 10,000, 1 ≤ Q**j, k ≤ 10,000을 만족한다. 상품의 이름은 알파벳 소문자로 이루어진 길이 1 이상 7 이하의 문자열이다. 그 밖의 값은 모두 정수이다. S**i는 모두 다르다. (X**j, Y**j)와 같은 순서쌍은 여러 번 나타나지 않고, (X**j, Y**j) = (0, 0)인 경우는 없다. 각 j에 대해 R**j, k는 모두 다르고, 각 R**j, k는 어느 S**i와 일치한다.
출력
토끼가 얻을 수 있는 최대 이익을 한 줄에 출력하라.