题目描述

小核桃去超市购物，她购物有以下习惯

1.每次购物至少去两个超市

2.总花费至少要达到 $k$ 元

3.每种物品至多买一个

如果存在某购物方案达不到上述的三个要求，那么小核桃会嫌买的东西太少，并且认为该购物方案非法。

现有 $n$ 个互不相同的物品，小核桃知道每个物品的价格和所在的超市，他想知道一共有多少种合法的购物方案。两种方案被认为不同当且仅当至少有一个物品的选取状态（购买/未购买）不同。

输出小核桃共有多少种合法购物方案，如果没有合法的购物方案，则输出 0。

输入格式

第 $1$ 行包括三个正整数 $n,m(2\le m\le n),k(0\le k\le 10^{18})$，分别代表物品个数、超市个数、总花费。

第 $2$ 行到第 $n+1$ 行每行两个正整数 $v_i(1\le v_i\le 10^{16}),s_i(1\le s_i\le m)$，代表第 $i$ 个物品的价格 $v_i$ 和该物品所在的超市 $s_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 \leq N \leq 20$ 且只有两种超市。

对于 40% 的数据，有 $2 \leq N \leq 20$

对于另外 30% 的数据，有 $N = 40$ ，只有两种超市，且每种超市 $20$ 个物品，$70$ 分。

对于 100% 的数据，有 $2 \leq N \leq 40$

大样例

大样例下载