9720: Tennis Match

The training team has $m$ candidate players, and now $2n$ players need to be selected and paired to participate in $n$ tennis doubles matches.

The $i$-th player has an estimated capability eie_iei and is classified into junior and senior categories based on their training duration.

The $i$-th match requires that the capability of any participating player does not exceed lil_ili, and for stability reasons, the coach requires that the capability difference between every two paired players does not exceed $d$.

Though there is no limitation for players to be paired based on the same category, in order to fully tap into the potential of junior players, the coach expects a few junior players to be selected for participation.

The coach tends to know, for each $t=0,1,\dots ,2n$, if there exists a pairing scheme that contains exactly $t$ junior players and also satisfies the above constraints. If no such scheme exists, output $-1$, or otherwise output the maximum possible sum of the ability values of the selected $2n$ players.

The first line contains an integer $T$ (1<=T<=10⁵), indicating the number of test cases.
Then follow $T$ test cases. For each test case:
The first line contains three integers $n$, $m$ and $d$ .
The second line contains $n$ integers l1,l2,…,lnl_1, l_2, \ldots, l_nl1,l2,…,ln (1<=l_i<=10⁹).
The next $m$ lines describe the candidate players' information, the $i$-th line of which contains two integers eie_iei and tit_iti (1<=e_i<=10⁹, ti∈{1,2}t_i \in \{1, 2\}ti∈{1,2}), indicating that the estimated capability of the $i$-th player is eie_iei, and is junior type if ti=1t_i = 1ti=1, or otherwise senior type.
It is guaranteed that the sum of $m$ across all $T$ test cases does not exceed 2*10⁵.

For each test case, output $(2n+1)$ integers in a line, where the $i$-th integer represents the answer with respect to selecting exactly $(i-1)$ junior players.