투표 의욕 꺾기

선거에서 가짜 뉴스는 자기 후보의 득표를 늘리기보다 상대 후보의 지지자가 투표장에 나오지 않게 만드는 데 쓰인다. 흔히 쓰는 방법은 특정 집단을 겨냥해 그 집단이 지지하는 후보의 부정적인 소식을 그 집단의 기존 편견에 들어맞는 형태로 퍼뜨리는 것이다. 이 문제는 그 상황을 다음과 같이 모형으로 옮긴다.

유권자 $j$는 좌우 정치 성향을 나타내는 축 위의 실수 위치 $x_j$에 있고, 위치가 0인 유권자는 없다. $x_j < 0$인 유권자는 좌파 후보에게, $x_j > 0$인 유권자는 우파 후보에게 투표한다. 유권자 $j$의 투표 성향은 $p_j$이다.

가짜 뉴스 $i$는 구간 $[\ell_i, r_i]$와 계수 $d_i$로 정해지며 $0 \le d_i \le 1$이다. 구간 $[\ell_i, r_i]$ 안에 있는 유권자가 이 뉴스에 노출되면 그 유권자의 투표 성향은 $p_j$에서 $p_j \times d_i$로 바뀐다.

캠프는 어떤 유권자도 두 개 이상의 구간에 들어가지 않도록 퍼뜨릴 가짜 뉴스의 집합을 고른다. 고른 구간 하나에 들어간 유권자는 그 뉴스에 노출된다. 고른 뉴스를 모두 퍼뜨린 뒤, 우파 후보에게 투표하는 유권자의 투표 성향 합에서 좌파 후보에게 투표하는 유권자의 투표 성향 합을 뺀 값을 최대로 만들어라.

첫째 줄에 데이터 집합의 개수 $K$가 주어진다($1 \le K \le 100$). 이어서 데이터 집합 $K$개가 차례로 주어진다.

각 데이터 집합의 첫째 줄에는 유권자 수 $n$과 가짜 뉴스 수 $m$이 주어진다($1 \le n \le 200$, $1 \le m \le 50$).

다음 $n$개 줄에는 유권자 $j$의 위치 $x_j$와 투표 성향 $p_j$가 주어진다($-1 \le x_j \le 1$, $x_j \ne 0$, $0 \le p_j \le 1$). 유권자는 $x_j$가 감소하지 않는 순서로 주어진다.

다음 $m$개 줄에는 가짜 뉴스 $i$의 $\ell_i$, $r_i$, $d_i$가 주어진다($-1 \le \ell_i \le r_i \le 1$, $0 \le d_i \le 1$). 가짜 뉴스는 $r_i$가 감소하지 않는 순서로 주어진다.

모든 수는 소수점 아래 두 자리까지만 주어진다. 어떤 $x_j$도 어떤 $\ell_i$나 $r_i$와 같지 않다.

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. 여기서 $x$는 1부터 시작하는 데이터 집합의 번호이다.

다음 줄에 우파 후보를 지지하는 유권자의 투표 성향 합에서 좌파 후보를 지지하는 유권자의 투표 성향 합을 뺀 값의 최댓값을 소수점 아래 두 자리로 반올림해 출력한다. 정확히 중간인 값은 0에서 먼 쪽으로 반올림한다. 즉 0.375는 0.38로, -0.125는 -0.13으로 출력한다. -0.00 대신 0.00을 출력한다.

각 데이터 집합 뒤에는 빈 줄을 하나 출력한다.