P6775 [NOI2020] 制作菜品

厨师准备给小朋友们制作 $m$ 道菜，每道菜均使用 $k$ 克原材料。为此，厨师购入了 $n$ 种原材料，原材料从 $1$ 到 $n$ 编号，第 $i$ 种原材料的质量为 $d_i$ 克。$n$ 种原材料的**质量之和恰好为 $m \times k$ 克**，其中 $d_i$ 与 $k$ 都是**正整数**。 制作菜品时，一种原材料可以被用于多道菜，但为了让菜品的味道更纯粹，厨师打算每道菜**至多使用 $2$ 种**原材料。现在请你判断是否存在一种满足要求的制作方案。更具体地，方案应满足下列要求： - 共做出 $m$ 道菜。 - 每道菜至多使用 $2$ 种原材料。 - 每道菜恰好使用 $k$ 克原材料。 - 每道菜使用的每种原材料的质量都为正整数克。 - $n$ 种原材料都被恰好用完。 若存在满足要求的制作方案，你还应该给出一种具体的制作方案。

无

无

#### 样例 1 解释 对于第二组数据，一种满足要求的制作方案为： - 使用 $80$ 克原材料 $1$ 与 $20$ 克原材料 $2$ 做第一道菜。 - 使用 $10$ 克原材料 $2$ 与 $90$ 克原材料 $3$ 做第二道菜。 - 使用 $100$ 克原材料 $4$ 做第三道菜。 #### 样例 2 见选手目录下的 dish/dish2.in 与 dish/dish2.ans。 #### 样例 3 见选手目录下的 dish/dish3.in 与 dish/dish3.ans。 --- ### 测试点约束 对于所有测试点： $1 \leq T \leq 10$，$1 \leq n \leq 500$，$n - 2 \leq m \leq 5000$，$m \geq 1$，$1 \leq k \leq 5000$，$\sum_{i=1}^{n}d_i = m \times k$。 每个测试点的具体限制见下表： | 测试点编号 | $n$ | $m$ | $k$ | | :-: | :-: | :-: | :-: | | $1\sim 3$ | $\le 4$ | $\le 4$ | $\le 50$ | | $4\sim 5$ | $\le 10$ | $\le 10$ | $\le 5\times 10^3$ | | $6\sim 7$ | $\le 500$ | $=n-1$ | $\le 5\times 10^3$ | | $8\sim 9$ | $\le 500$ | $n-1\le m\le 5\times 10^3$ | $\le 5\times 10^3$ | | $10$ | $\le 25$ | $\le 5\times 10^3$ | $\le 5\times 10^3$ | | $11\sim 12$ | $\le 25$ | $\le 5\times 10^3$ | $\le 500$ | | $13\sim 14$ | $\le 50$ | $\le 5\times 10^3$ | $\le 500$ | | $15\sim 17$ | $\le 100$ | $\le 5\times 10^3$ | $\le 5\times 10^3$ | | $18\sim 20$ | $\le 500$ | $\le 5\times 10^3$ | $\le 5\times 10^3$ |