购物方案

题目背景

育华学校开展生活实践课程，其中一项任务是根据校园周边超市的购物规则，统计符合特定要求的合法购物方案数量。这项任务有助于同学们理解组合数学在实际生活中的应用，提升算法设计与问题解决能力。

题目描述

在校园周边购物时，需遵循以下规则：

1. 每次购物至少要去两个不同的超市；
2. 总花费至少要达到 $k$ 元；
3. 每种物品至多购买一个。

若不满足以上任何一条，均视为非法购物方案。

现有 $n$ 个不同的物品，每个物品对应一个价格和所属超市。请计算符合要求的合法购物方案总数（两种方案不同的判定标准：至少有一个物品的选取状态不同）。若没有合法方案，输出 $0$。

输入格式

第一行输入三个正整数 $n, m, k$（$2 \leq m \leq n$，$0 \leq k \leq 10^{18}$），分别代表：

• $n$：物品个数；
• $m$：超市个数；
• $k$：总花费下限。

接下来 $n$ 行，每行输入两个正整数 $v_i$（$1 \leq v_i \leq 10^{16}$）和 $s_i$（$1 \leq s_i \leq m$），代表第 $i$ 个物品的价格和所属超市。

输出格式

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

样例

样例输入 1

3 2 2
11 1
12 2
2 1

样例输出 1

3

样例解释 1

符合条件的方案：

1. 选物品 1（超市 1，价格 11）+ 物品 2（超市 2，价格 12）→ 涉及 2 个超市，总花费 23 ≥ 2；
2. 选物品 2（超市 2，价格 12）+ 物品 3（超市 1，价格 2）→ 涉及 2 个超市，总花费 14 ≥ 2；
3. 选物品 1 + 物品 2 + 物品 3 → 涉及 2 个超市，总花费 25 ≥ 2；

共 3 种合法方案。

样例输入 2

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

样例输出 2

50

数据范围与测试点（共20个测试点）