题目背景

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

一切，就这么结束了吗？

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

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

题目描述

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

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

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

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

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

1. 将一节光明程度为 $a$ 的蜈蚣的光明程度 变为 $b$。（注意，$b$ 可能 $<=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 <= a,b,a1,b1,a2,b2 <= 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 <= 3$

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

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

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

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

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

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

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