P5029 T'ill It's Over

小正方形被黑暗之主碾成了粉末。 一切，就这么结束了吗？ 就当大家都以为再无翻盘的希望时， 已经被净化的两个世界之树的部分，微微闪烁……

小正方形被三角的力量复活了，它即将与黑暗之主展开最后的战斗。 小正方形最后的目标，就是净化黑暗之主。 黑暗之主的蜈蚣长度为 $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$

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

首先使用方案 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**。 **数据保证，操作为随机生成**。