我们正在举办一场珠宝展览。你的任务是确保珠宝在夜间的安全。

有 $k$ 名保安可用。对于每名保安，已知其在夜间可以工作的时间。我们假设每个夜晚被划分为 $n$ 个时间单位。如果在夜间至少有 $m$ 个时间单位中，珠宝被至少两名保安看守，则认为珠宝是安全的。

为了防止保安被贿赂，你希望每晚选择不同的保安子集，以便珠宝在每晚都是安全的。计算存在多少个这样的子集。

输入格式

第一行包含三个整数 $n$、$k$ 和 $m$（$1 \le n \le 10^9$，$2 \le k \le 20$，$1 \le m \le n$），分别表示夜晚的时间单位数、保安人数，以及珠宝必须被至少两名保安看守的最小时间单位数。

接下来的 $k$ 行描述了每名保安可以工作的时间区间。每行以一个非负整数 $c_i$（$i \in \{1, \dots, k\}$）开始，表示时间区间的数量。随后是 $c_i$ 对整数 $a_{i,j}, b_{i,j}$（$j \in \{1, \dots, c_i\}$），描述区间 $[a_{i,j}, b_{i,j}]$，表示第 $i$ 名保安从时间单位 $a_{i,j}$ 工作到时间单位 $b_{i,j}$（含端点）。这些区间两两不相交，并按左端点递增的顺序给出。

你可以假设 $c_1 + c_2 + \dots + c_k \le 10^6$。

输出格式

输出应包含一个非负整数，表示可以选出的保安子集数量，使得珠宝在夜间是安全的。

样例

输入样例 1

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

输出样例 1

2

说明

所求的保安子集为 $\{1, 3\}$ 和 $\{1, 2, 3\}$。第一名和第三名保安共同看守珠宝的时间有六个时间单位，即 $\{1, 2, 4, 8, 9, 10\}$。如果选择所有三名保安，则珠宝在八个时间单位 $\{1, 2, 3, 4, 5, 8, 9, 10\}$ 内被至少两名保安看守。