描述
小B在学校科技节上参加了一个天平游戏。桌上有 $n$ 块石头，编号为 $1,2,\ldots,n$。每块石头都被涂成红色或蓝色，第 $i$ 块石头的重量为 $a_i$。
小B先从桌上恰好拿走一块红色石头和一块蓝色石头，再从剩下的石头中选出最重的 $k$ 块，放入天平左边的托盘，其余石头全部放入天平右边的托盘。如果两个托盘中石头的总重量相差不超过 $\Delta$，这次选择就符合游戏要求。
请计算有多少种拿走石头的方案符合要求。两种方案只要拿走的石头编号不完全相同，就算作不同的方案。
如果有多块石头重量相同，使得最重的 $k$ 块石头有不止一种选法，可以任意采用其中一种选法。不同的选法不会改变两个托盘中石头的总重量，因此不另外计数。
输入
从文件 ***balance.in*** 中读入数据。
第一行包含一个整数 $T$，表示数据组数。
对于每组数据：
第一行包含三个整数 $n,k,\Delta$，分别表示石头的数量、放入天平左边托盘的石头数量，以及两个托盘中石头总重量允许相差的最大值。
接下来共有 $n$ 行。第 $i$ 行包含两个整数 $a_i,c_i$，分别表示第 $i$ 块石头的重量和颜色。其中，$c_i=0$ 表示红色，$c_i=1$ 表示蓝色。
输出
将结果输出到文件 ***balance.out*** 中。
对于每组数据，输出一行，包含一个整数，表示符合游戏要求的方案数量。
样例
- 复制
- 复制
提示
## 样例解释
第 1 组数据中，只有 6 号石头是蓝色，因此拿走的两块石头中必须包含 6 号石头。
拿走 5 号石头和 6 号石头后，剩下的四块石头重量均为 $1$。两个托盘中各放两块石头，总重量都为 $2$，符合要求。如果拿走任意一块重量为 $1$ 的红色石头和 6 号石头，剩下的四块石头重量为 $1,1,1,2$。左边托盘中最重的两块石头总重量为 $3$，右边托盘中的石头总重量为 $2$。本组数据要求两个托盘中的石头总重量完全相等，因此这种选择不符合要求。只有拿走 5 号石头和 6 号石头的方案符合要求，答案为 $1$。
第 2 组数据与第 1 组数据使用相同的石头，只把 $\Delta$ 从 $0$ 改为 $1$。此时，拿走任意一块红色石头和 6 号石头，两个托盘中石头的总重量都相差不超过 $1$。共有五块红色石头，因此答案为 $5$。
第 3 组数据中，拿走 1 号石头和 2 号石头后，剩下的两块石头重量均为 $2$；拿走 3 号石头和 4 号石头后，剩下的两块石头重量均为 $1$。这两种方案都符合要求。其他拿走一块红色石头和一块蓝色石头的方案，会剩下一块重量为 $1$ 的石头和一块重量为 $2$ 的石头，不符合要求，因此答案为 $2$。
## 数据范围与测试点
对于所有数据，保证 $1\le T\le100$，$4\le n\le2\times10^5$，$1\le k\le n-3$，$1\le a_i\le10^9$，$c_i\in\{0,1\}$，$0\le\Delta\le10^{15}$。同一输入文件中，所有数据组的 $n$ 之和不超过 $2\times10^5$。
下表中的限制对对应测试点中的每组数据均成立。“—”表示除上述通用数据范围外，没有额外限制。
| 测试点编号 | $n$ | $T$ | 特殊性质 | 分值 |
|:---:|:---:|:---:|:---:|:---:|
| 1 | $n\le60$ | $T\le20$ | — | 5 |
| 2 | $n\le60$ | $T\le20$ | — | 5 |
| 3 | $n\le3000$ | $T\le10$ | — | 5 |
| 4 | $n\le3000$ | $T\le10$ | — | 5 |
| 5 | $n\le3000$ | $T\le10$ | — | 5 |
| 6 | $n\le3000$ | $T\le10$ | — | 5 |
| 7 | — | — | A | 5 |
| 8 | — | — | A | 5 |
| 9 | — | — | B、C | 5 |
| 10 | — | — | B、C | 5 |
| 11 | — | — | B | 5 |
| 12 | — | — | B | 5 |
| 13 | — | — | C | 5 |
| 14 | — | — | C | 5 |
| 15 | — | — | — | 5 |
| 16 | — | — | — | 5 |
| 17 | — | — | — | 5 |
| 18 | — | — | — | 5 |
| 19 | — | — | — | 5 |
| 20 | — | — | — | 5 |
特殊性质 A：对于所有 $1\le i\le n$，均有 $a_i\in\{1,2\}$。
特殊性质 B：$k=1$。
特殊性质 C：$\Delta=0$。
同一行列出的多个特殊性质同时成立。每个测试点单独计分，每个测试点为 5 分，总分为 100 分。一个测试点输入文件中的所有数据组均回答正确时，获得该测试点的分值。
关注我们
