题目背景

小正方形被黑暗之主碾成了粉末。

一切，就这么结束了吗？

就当大家都以为再无翻盘的希望时，

已经被净化的两个世界之树的部分，微微闪烁……

题目描述

小正方形被三角的力量复活了，它即将与黑暗之主展开最后的战斗。

小正方形最后的目标，就是净化黑暗之主。

黑暗之主的蜈蚣长度为 $n$，一开始每一节的光明程度为 $1$。

当一节蜈蚣的光明程度达到一个指定的值 ($k$)，我们就视作这节蜈蚣被净化。

为了净化黑暗之主，小正方形准备了 $m$ 种方案，这些方案按本质上的不同大约可分为四种：

1. 将一节光明程度为 $a$ 的蜈蚣的光明程度 变为 $b$。（注意，$b$ 可能 $\le a$）

2. 将一节光明程度在 $a1$ 到 $a2$ 区间的蜈蚣的光明程度变为 $b1$。

3. 将一节光明程度为 $a1$ 的蜈蚣的光明程度变为 $b1$ 到 $b2$ 区间的任意值。

4. 将一节光明程度在 $a1$ 到 $a2$ 区间的蜈蚣的光明程度变为 $b1$ 到 $b2$ 区间的任意值。

由于小正方形使用每种方案需要消耗一定程度的属性能量，因此每种方案都有一个独立的使用次数的上限，在一种方案中我们用 $l$ 来表示这个上限。

小正方形想要知道，自己最多能够净化几节黑暗之主的蜈蚣。

输入格式

第一行为三个正整数 $n,m,k$，表示黑暗之主蜈蚣身体的长度，小正方形的方案总数与上文所述的 $k$。

接下来 $m$行，每行开头为两个正整数 $op,l$，表示方案的种类与使用次数的上限，方案的输入方式如下：

若 $op = 1$，则接下来两个整数 $a,b$，意义如上文所述。

若 $op = 2$，则接下来三个整数 $a1,a2,b1$，意义如上文所述。

若 $op = 3$，则接下来三个整数 $a1,b1,b2$，意义如上文所述。

若 $op = 4$，则接下来四个整数 $a1,a2,b1,b2$，意义如上文所述。

数据保证，所有 $1 \le a,b,a1,b1,a2,b2 \le k$

输出格式

一行一个整数，表示最多能净化的节数。

5 4 5
1 3 1 3
1 3 3 2
1 3 2 5
4 1 1 1 4 5

4

提示

首先使用方案 1，2，3，将三节光明程度变为 $3$，接着再变为 $2$，再变为 $5$。

然后使用方案 4，将一节的光明程度变为 $5$。

对于 $10\%$ 的数据，$n = 1,op = 1$。

对于另外 $10\%$ 的数据，$n = 1,op \le 3$。

对于另外 $10\%$ 的数据，$n \le 10,op = 1$。

对于另外 $20\%$ 的数据，$n \le 100,m \le 100,op = 1$。

对于 $70\%$ 的数据，$n \le 1000,m \le 1000,op \le 3,k \le 20000$。

对于前 $70\%$ 的数据，时限为 $500$ ms。

对于 $100\%$ 的数据，$n \le 10^7,m \le 20000,1 \le k \le 10^5,1 \le l \le 10^5$。

对于后 $30\%$ 的数据，时限为 $8000$ ms。

数据保证，操作为随机生成。