该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

岐岐正在计划一次超市购物，她有以下习惯：

1. 每次至少要去两家不同的超市；
2. 总花费至少要达到 $k$ 元；
3. 每种物品至多购买一个。
   若某种购物方案不满足上述任一条件，则视为非法。

题目描述

现有 $n$ 件互不相同的物品，编号为 $1$ 到 $n$。第 $i$ 件物品的价格为 $v_i$，所在的超市编号为 $s_i$。请计算共有多少种合法的购物方案。两种方案被认为不同当且仅当在至少一件物品上，购买/未购买的状态不同。

输出合法购物方案的总数；若不存在合法方案，则输出 $0$。

输入格式

第一行包含三个正整数

分别表示物品个数、超市个数和总花费下限。
接下来 $n$ 行，每行包含两个正整数

分别表示第 $i$ 件物品的价格和所在超市编号。

输出格式

输出一个整数，表示合法的购物方案数。

样例

3 2 2
11 1
12 2
2 1

3

6 3 10
4 1
5 1
3 2
6 2
8 3
10 1

50

样例解释

样例 1 中，合法的购物方案为 {1,2}、{2,3}、{1,2,3}，共 3 种。

数据范围

• 对于 20% 的数据，$2 \le n \le 20$ 且 $m=2$。
• 对于 40% 的数据，$2 \le n \le 20$。
• 对于 30% 的数据，$n=40,\;m=2$ 且每个超市恰有 20 件物品。
• 对于 100% 的数据，$2 \le n \le 40$。