T'ill It's Over

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

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