Voter Depression

In an election, fake news is used to keep the other candidate's supporters at home rather than to raise turnout for your own side. The usual method targets a specific group with negative messages about the candidate that group supports, shaped to fit biases the group already holds. This problem models that situation as follows.

Voter $j$ sits at a real position $x_j$ on an axis that runs from the political left to the political right, and no voter sits at 0. A voter with $x_j < 0$ votes for the left candidate, and a voter with $x_j > 0$ votes for the right candidate. Voter $j$ has propensity $p_j$ to vote.

Fake news story $i$ is given by an interval $[\ell_i, r_i]$ and a factor $d_i$ with $0 \le d_i \le 1$. When a voter inside $[\ell_i, r_i]$ is exposed to that story, the propensity of that voter changes from $p_j$ to $p_j \times d_i$.

The campaign selects a set of stories to deploy so that no voter falls inside two or more of the selected intervals. A voter inside one selected interval is exposed to that story. After all selected stories are deployed, maximize the total propensity of the voters who vote for the right candidate minus the total propensity of the voters who vote for the left candidate.

The first line contains the number of data sets $K$ ($1 \le K \le 100$). The $K$ data sets follow in order.

The first line of a data set contains the number of voters $n$ and the number of fake news stories $m$ ($1 \le n \le 200$, $1 \le m \le 50$).

Each of the next $n$ lines contains the position $x_j$ and the propensity $p_j$ of voter $j$ ($-1 \le x_j \le 1$, $x_j \ne 0$, $0 \le p_j \le 1$). The voters are given in non-decreasing order of $x_j$.

Each of the next $m$ lines contains $\ell_i$, $r_i$ and $d_i$ of story $i$ ($-1 \le \ell_i \le r_i \le 1$, $0 \le d_i \le 1$). The stories are given in non-decreasing order of $r_i$.

Every number is given with at most two digits after the decimal point. No $x_j$ equals any $\ell_i$ or any $r_i$.

For each data set, first print Data Set x: on a line of its own, where $x$ is the number of the data set counting from 1.

On the next line print the largest achievable value of the total propensity of the voters for the right candidate minus the total propensity of the voters for the left candidate, rounded to two digits after the decimal point. A value exactly halfway between two outputs rounds away from zero, so 0.375 prints as 0.38 and -0.125 prints as -0.13. Print 0.00 rather than -0.00.

Print a blank line after each data set.