토목 공학

토목 공학은 구조물이 무너지지 않도록 짓는 방법을 다룬다(반면 건축가는 겉모습에 더 관심을 둔다). 이러한 구조물에는 지진이 잦은 지역의 건물이나 허리케인이 잦은 지역의 댐 등이 있다. 여기서는 건물 시공과 관련된 간단한 문제를 다룬다.

어떤 부지 위에 건물을 세우려고 하는데, 건물의 총 무게에 제한이 있다고 하자. 제안된 시공이 이 무게 제한을 넘는지 확인하는 일은 꽤 번거로울 수 있으므로, 토목 기술자를 대신하여 이를 계산하는 프로그램을 작성하라.

건물은 여러 개의 직육면체(3차원 직사각형 블록)를 조립하여 만든다. 각 직육면체에는 크기(높이, 너비, 깊이)와 그것을 이루는 재질 정보가 함께 주어진다. 또한 각 재질마다 밀도(단위 부피당 무게)가 주어진다. 모든 직육면체의 총 무게를 구하라.

첫째 줄에 데이터 집합의 개수 $K \ge 1$이 주어진다. 이어서 $K$개의 데이터 집합이 다음 형식으로 주어진다.

각 데이터 집합의 첫째 줄에는 두 정수 $m$, $n$이 주어진다($1 \le m, n \le 10000$). $m$은 데이터베이스에 있는 재질의 수이고, $n$은 건물을 이루는 직육면체의 수이다.

다음 $m$개의 줄에는 각 재질의 밀도가 한 줄에 하나씩 주어진다. 밀도는 그램 매 세제곱센티미터 단위의 음이 아닌 정수이다.

다음 $n$개의 줄에는 각각 네 정수 $h$, $w$, $d$, $i$가 주어진다. $h$, $w$, $d$는 직육면체의 높이, 너비, 깊이(센티미터)이고, $i$는 그 재질의 번호이다. $h$, $w$, $d$는 음이 아닌 정수이며, $i$는 $1$ 이상 $m$ 이하의 정수이다.

모든 입력에 대해 총 무게는 부호 있는 32비트 정수 범위 안에 들어감이 보장된다.

각 데이터 집합마다 먼저 "Data Set x:"를 한 줄에 출력한다. 여기서 $x$는 데이터 집합의 번호($1$부터 시작)이다. 그다음 줄에 직육면체들의 총 무게를 그램 단위로 출력한다.