Description：

$n$ 块奶酪 $m$ 只老鼠，第 $i$ 只老鼠吃的速度是 $s_i$ ，第 $i$ 块奶酪的大小为 $p_i$ ，要求任意时刻一块奶酪最多被一只老鼠吃，一只老鼠最多吃一块奶酪，每块奶酪必须在 $d_i$ 前吃完，但是可以把所有奶酪延时 $T$ ，求 $T$ 的最小值。

$1\leqslant n,m\leqslant 30$

Solution：

首先每个老鼠同一时刻只吃一块奶酪比较好解决，我们只要让老鼠吃的总量大于等于奶酪的总量就总能分配老鼠在同一时刻只吃一块奶酪，如果不考虑另一个条件，我们可以这样建图：

先二分一个时间 $T$ ，然后把所有出现奶酪或者奶酪消失的时间点离散化，这样我们就知道了每个时间段内有哪些奶酪，然后把老鼠按照时间段拆点，和奶酪连 $\infty$ 边，和汇点连容量为这段时间能吃的量的边就行了。

现在我们只要解决不能有多只老鼠同时吃一块奶酪，太神了开始念题解：

我们在把老鼠按时间段拆点之后再把所有老鼠的速度按从大到小排序，在最后加一个 $0$ 之后差分，得到 $m$ 个数，再拆成 $m$ 个点，把这些数看成新的速度然后和奶酪相连，然后和汇点连的边为 $i\times v[i]\times t$ ， $i$ 是下标。

这样神奇的连边方式，首先每只老鼠贡献的流量一定是合法的（因为乘了一个 $i$ ）：

$9,6,2,1\to 3,4,1,1\Rightarrow 9+6+1+1=3\times 1+4\times 2+1\times 3+1\times 4$

也就是说保证了最后流的总量一定是实际可以吃的下的，那么就可以安排老鼠同一时刻只吃一块奶酪了。

然后考虑他是怎么保证每块奶酪同一时刻只被一只老鼠吃的：由于奶酪和老鼠之间的边为 $v[i]\times t$ ，并没有乘上 $id$ ，而且这个是差分之后的结果，于是就算很多条流加起来还是可以给一只老鼠吃。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 70

int p[MAXN],r[MAXN],d[MAXN];

int s[MAXN];

#define MAXP (MAXN + MAXN * MAXN)

#define MAXE (MAXN + MAXN * MAXN + MAXN * MAXN * MAXN)

struct edge

{

    int to,nxt;

	double f;

}e[MAXE << 1];

int edgenum = 0;

int lin[MAXP] = {0};

void add(int a,int b,double f)

{//cout << a << " " << b << " " << f << endl;

    e[edgenum] = (edge){b,lin[a],f};lin[a] = edgenum++;

    e[edgenum] = (edge){a,lin[b],0};lin[b] = edgenum++;

    return;

}

int S,T;

#define INF 0x3f3f3f3f

int ch[MAXP];

bool BFS()

{

    memset(ch,-1,sizeof(ch));ch[S] = 0;

    queue<int> q;q.push(S);

    while(!q.empty())

    {

        int k = q.front();q.pop();

        for(int i = lin[k];i != -1;i = e[i].nxt)

        {

            if(ch[e[i].to] == -1 && e[i].f)

            {

                ch[e[i].to] = ch[k] + 1;

                q.push(e[i].to);

            }

        }

    }

    return (ch[T] != -1);

}

double flow(int k,double f)

{

    if(k == T)return f;

    double r = 0;

    for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

    {

        if(ch[e[i].to] == ch[k] + 1 && e[i].f)

        {

            double l = flow(e[i].to,min(e[i].f,f - r));

            e[i].f -= l;r += l;e[i ^ 1].f += l;

        }

    }

    if(r == 0)ch[k] = -1;

    return r;

}

double dinic()

{

    double ans = 0,r;

    while(BFS())while(r = flow(S,INF))ans += r;//cout << ans << endl;

    return ans;

}

int tot = 0;

int cntp;

double b[MAXN * 2];

int id[MAXN * 2][MAXN];

int sum = 0;

bool check(double v)

{

	edgenum = 0;

	memset(lin,-1,sizeof(lin));

	tot = 0;

	for(int i = 1;i <= n;++i)b[++tot] = r[i],b[++tot] = d[i] + v;

	sort(b + 1,b + 1 + tot);

	tot = unique(b + 1,b + 1 + tot) - b - 1;

	S = n + (tot - 1) * m + 1;T = S + 1;

	cntp = n;

	for(int i = 1;i < tot;++i)for(int j = 1;j <= m;++j)id[i][j] = ++cntp;

	//cout << cntp << endl;

	for(int i = 1;i <= n;++i)add(S,i,p[i]);

	for(int i = 1;i <= n;++i)

	{

		int x = lower_bound(b + 1,b + 1 + tot,r[i]) - b;

		int y = lower_bound(b + 1,b + 1 + tot,d[i] + v) - b;

		for(int j = x;j < y;++j)

		{

			for(int k = 1;k <= m;++k)

			{

				add(i,id[j][k],s[k] * (b[j + 1] - b[j]));

			}

		}

	}

	for(int j = 1;j < tot;++j)

	{

		for(int k = 1;k <= m;++k)

		{

			add(id[j][k],T,k * s[k] * (b[j + 1] - b[j]));

		}

	}//cout << sum << " : ";

	return dinic() == sum;

}

bool cmp(int a,int b){return a > b;}

void work()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d%d%d",&p[i],&r[i],&d[i]);

	sum = 0;

	for(int i = 1;i <= n;++i)sum += p[i];

	for(int i = 1;i <= m;++i)scanf("%d",&s[i]);

	sort(s + 1,s + 1 + m,cmp);

	s[m + 1] = 0;

	for(int i = 1;i <= m;++i)s[i] -= s[i + 1];

	double l = 0,r = 1000000000,mid;

	while(r - l > 1e-9)

	{

		mid = (l + r) / 2;

		if(check(mid))r = mid;

		else l = mid;

	}

	printf("%.4lf\n",l);

	return;

}

int main()

{

	int testcases = rd();

	while(testcases--)work();

	return 0;

}