Advertising Revenue

Time limit2sMemory limit512 MB

Summary

For each data set, sum the payments for every display ad shown and every clickthrough ad clicked, then print the total.

Level: Easy2 of 10
Topics: Implementation, Simulation
Solved: No attempts yet

Problem

One motivation for producing fake news stories is money. The site earns from ads that are shown to its visitors or clicked on by them. Mysterious, surprising, or scandalous stories attract a lot of readers, which is why fake news headlines are often outrageous and vague ("You won't believe ...").

Online ads usually come in two forms. For a display ad, the advertiser pays the site just for showing the ad. The idea is to build brand recognition. For a clickthrough ad, the advertiser pays only when a visitor clicks the ad. The idea is that some fraction of clicks leads to purchases, now or later. Prices for online ads run from a few cents per display or click up to $100 per click. (The advertisers who pay $100 per click are class-action lawyers.)

You are given a list of ads, both clickthrough and display, together with a history of visitors that records what each visitor saw and what each visitor clicked. Calculate how much money the fake news site made.

Input

The first line contains the number $K$ of data sets in the file, where $K \ge 1$ . Then come $K$ data sets of the following form.

The first line of each data set contains two integers $n$ , $v$ . Here $2 \le n \le 1000$ is the number of ads the site has as customers, and $0 \le v \le 1000$ is the number of visitors to the site.

The next $n$ lines each describe one ad $i$ with two integers $d_i$ , $p_i$ . The value $d_i$ is either 0 or 1. A value of 1 means the ad is a display ad, so the site gets paid just for showing it. A value of 0 means the ad is a clickthrough ad, so the site gets paid only when a visitor clicks it. $1 \le p_i \le 1000$ is the payment for the ad, paid for each display of a display ad and for each click on a clickthrough ad.

The next $v$ lines each describe one visitor $j$ with three integers $a_{j,1}$ , $a_{j,2}$ , $c_j$ . The first two numbers are the two ads the visitor is shown. They are distinct and lie between 1 and $n$ , inclusive. The number $c_j \in \{0, 1, 2\}$ is the ad the visitor clicked on. A value of 0 means the visitor clicked nothing, 1 means the visitor clicked $a_{j,1}$ , and 2 means the visitor clicked $a_{j,2}$ . A visitor may click a display ad, and the site gets no extra payment for that.

Output

For each data set, first output Data Set x: on a line by itself, where $x$ is its number. On the next line, output the total payment that the site receives. Follow each data set with a blank line.

Examples6

Example 1

Input

Expected output

Data Set 1:
150

Data Set 2:
40

Example 2
Input
```
1
2 0
0 1
1 1
```
Expected output
```
Data Set 1:
0
```

Example 3

Input

Expected output

Data Set 1:
0

Example 4

Input

Expected output

Data Set 1:
80

Example 5

Input

Expected output

Data Set 1:
1250

Example 6

Input

Expected output

Data Set 1:
2000

Data Set 2:
0

Data Set 3:
60

Data Set 4:
2