- 有(n)种原材料，分别有(d_i)克，满足(sum d_i=m imes k)。
- 要求制作(m)道菜，满足每道菜使用至多两种原材料，且恰好使用(k)克。
- 构造一种合法方案，或判断无解。
- 数据组数(le10)，(nle500,n-2le mle5 imes10^3)
(m=n-1)的构造方案
将所有(d_i)排序，然后就会发现两个很显然却很有用的结论：
- (d_1<k)。如果(d_1ge k)，则(sum d_ige nk>(n-1)k)。
- (n>2)时，(d_n>k-d_1)。如果(d_nle k-d_1)，则(sum d_ile d_1+(n-1)(k-d_1)=(n-1)k-(n-2)d_1<(n-1)k)。
注意第二个结论虽然只适用于(n>2)，但(n=2)的时候显然(d_1+d_n=k)直接构造就好了。
而当(n>2)时，根据上面这两个结论，我们必然可以用光所有的(d_1)，并从(d_n)中取出一部分与它配对。
这样一来原材料少了一种（(n)减(1)），菜制成了一道（(m)减(1)），依然满足(m=n-1)，可以继续按照这种方式构造下去。
由于这种构造方案不取决于(d_i)的具体值，也就是说对于任意(m=n-1)的情况，都必然存在一种合法方案。
(mge n)的直接转化
如果(mge n)，说明(sum d_i=mkge nk)，因此(d_nge k)。
所以我们必然能用(d_n)制成一道菜（(m)减(1)），一直这样转化下去直至(m=n-1)，然后就可以用上面的方法继续构造了。
(m=n-2)的大力拆分
如果我们在制成同一道菜的原材料之间连边，那么总共只能连出(m=n-2)条边，所以至少会被分成两个连通块。
不同连通块中的原材料之间是互不影响的，而如果我们只考虑将所有原材料划分成两个集合(S_1,S_2)，那么只要让两个集合分别制成(|S_1|-1)和(|S_2|-1)道菜，根据先前的结论显然一定有合法方案，且拼起来又恰好是(n-2)道菜。
因此，现在只要考虑如何把所有的原材料划分为两个集合，满足两个集合中的(d_i)的总和分别是((|S_1|-1) imes k)和((|S_2|-1) imes k)。
由于全部(d_i)的总和就是((n-2) imes k)，因此实际上只要满足其中一个条件，那么另一个条件自然也就满足了。
所以现在的问题就是找到一个集合(S_1)满足(sum_{iin S_1}d_i=(|S_1|-1) imes k)。
把右式的(|S_1| imes k)移到左式的(sum)中去，就变成了(sum_{iin S_1}(d_i-k)=-k)。
这怎么看都是一个(01)背包问题啊！
而这种仅需判有解、构造任意一组合法方案的问题，显然可以(bitset)优化。
至此，所有的情况都讨论完了，不得不说这道题真的是一道思维好题。
代码：(O(Tfrac{n^2k}{32}))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 500
#define K 5000
#define V (N*K)
using namespace std;
int n,m,k,a[N+5],id[N+5];I bool cmp(CI x,CI y) {return a[x]<a[y];}
I void Solve(CI n,int* id)//用n种原材料制成n-1道菜，id是排序后的编号
{
for(RI i=1,j;i<=n-1;++i)//制成n-1道菜
{
printf("%d %d %d %d
",id[i],a[id[i]],id[n],k-a[id[i]]),a[id[n]]-=k-a[id[i]];//把i和n拼成一道菜
for(j=n-1;j^i;--j) a[id[j]]>a[id[j+1]]&&(swap(id[j],id[j+1]),0);//最大值改变，维护大小顺序（显然可以堆优化，但无意义）
}
}
bitset<2*V+5> S[N+5];int s[N+5],p[N+5];I void Bag()//01背包划分集合
{
RI i;for(S[0].set(V),i=1;i<=n;++i) a[id[i]]>k
?(S[i]=S[i-1]|S[i-1]<<a[id[i]]-k):(S[i]=S[i-1]|S[i-1]>>k-a[id[i]]);//bitset优化01背包
if(!S[n].test(V-k)) return (void)puts("-1");//无解
RI t=V-k;for(i=n;i;--i) p[i]=S[i-1].test(t-(a[id[i]]-k))?(t-=a[id[i]]-k,1):0;//找一组合法方案
for(t=0,i=1;i<=n;++i) p[i]&&(s[++t]=id[i]);Solve(t,s);//对于第一个点集
for(t=0,i=1;i<=n;++i) !p[i]&&(s[++t]=id[i]);Solve(t,s);//对于第二个点集
}
int main()
{
RI Tt,i;scanf("%d",&Tt);W(Tt--)
{
for(scanf("%d%d%d",&n,&m,&k),i=1;i<=n;++i) scanf("%d",a+i),id[i]=i;
sort(id+1,id+n+1,cmp);W(m>=n) {for(printf("%d %d
",id[n],k),//把m≥n转化成m=n-1
a[id[n]]-=k,--m,i=n-1;i;--i) a[id[i]]>a[id[i+1]]&&(swap(id[i],id[i+1]),0);}//用n做一道菜，维护大小顺序
m==n-2?Bag():Solve(n,id);
}return 0;
}