Civil Engineering

Civil engineering is concerned with how to build structures so that they do not collapse (whereas architects care more about how things look). Such structures include buildings in an earthquake-prone area, or dams in a hurricane-prone area. Here we look at a simple problem related to building construction.

Suppose you want to place a building on a plot of land, but you have a limit on the building's total weight. Checking whether a proposed construction exceeds that weight can be quite a chore, so we ask you to write a program that takes care of it for civil engineers.

The building is described as a collection of oblongs (rectangular 3-dimensional blocks) that are assembled to form the building. Each oblong comes with its dimensions (height, width, depth) and the material it is made from. In addition, for each material you are given its density (weight per unit volume). Compute the total weight of all the oblongs.

The first line contains an integer $K \ge 1$, the number of data sets. Then follow $K$ data sets, each of the following form.

The first line of a data set contains two integers $m$ and $n$ (both between $1$ and $10000$): $m$ is the number of materials in the database, and $n$ is the number of oblongs in the building.

The next $m$ lines each contain the density of one material, a non-negative integer in grams per cubic centimeter.

The next $n$ lines each contain four integers $h$, $w$, $d$, $i$: the height, width, and depth of an oblong (in centimeters), and the index $i$ of its material. $h$, $w$, $d$ are non-negative integers, and $i$ is an integer between $1$ and $m$.

For every input it is guaranteed that the total weight fits in a signed 32-bit integer.

For each data set, first output a line "Data Set x:" by itself, where $x$ is the data set number (starting from $1$). Then, on the next line, output the total weight of the oblongs in grams.