题目描述

校集训队有 $m$ 位候选队员，现在需要选出 $2n$ 位队员两两配对组合，参加 $n$ 场网球双打比赛。 第 $i$ 名队员有一个预估能力值 $e_i$，并按照参训时长分为初级和高级两类。 第 $i$ 场比赛要求参赛选手的能力值均不超过 $l_i$，且出于稳定性考虑，教练要求每组配对的两名队员能力值相差不超过 $d$。

虽然没有限制球员必须基于相同类别进行配对，但是为了充分挖掘初级队员的潜力，教练们希望选出一定初级队员参赛。

教练想知道，对于 $t = 0,1,\dots,2n$，是否存在恰好选出 $t$ 名初级队员又满足上述约束的配对方案。如果不存在这样的方案，输出 $-1$，否则输出所选 $2n$ 名球员的能力值的最大可能总和。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 10^5$），表示测试用例的数量。接下来是 $T$ 个测试用例。对于每个测试用例：

• 第一行包含三个整数 $n, m$ 和 $d$（$1 \le n \le 20,\; 2n \le m \le 10^5,\; 0 \le d < 10^9$）。
• 第二行包含 $n$ 个整数 $l_1, l_2, \dots, l_n$（$1 \le l_i \le 10^9$），表示第 $i$ 场比赛允许参赛选手的能力上限。
• 接下来 $m$ 行描述候选队员信息，第 $i$ 行包含两个整数 $e_i$ 和 $t_i$（$1 \le e_i \le 10^9,\; t_i \in \{1,2\}$），表示第 $i$ 名队员的预估能力值为 $e_i$，若 $t_i=1$ 则为初级类型，否则为高级类型。

保证所有测试用例中 $m$ 之和不超过 $2\times10^5$。

输出格式

对于每个测试用例，在一行中输出 $2n+1$ 个整数，第 $i$ 个整数表示恰好选出 $i-1$ 名初级队员时的答案（即最大可能的总能力值），如果不存在满足约束的配对方案则输出 $-1$。

输入输出样例 #1

输入 #1

2
4 9 400
800 900 1050 1200
46 1
264 2
295 1
305 1
332 2
678 1
770 2
903 2
1291 2
4 9 400
800 900 1050 1200
46 1
264 2
295 1
305 2
332 2
678 2
770 2
903 2
1291 1

输出 #1

-1 -1 -1 -1 3593 -1 -1 -1 -1
-1 -1 3593 -1 -1 -1 -1 -1 -1