题目描述

尽管农夫约翰在集市上四处走动以收集奖品或观看表演没有问题，但他的奶牛们却没有那么好的体力；在集市上走一天会让它们筋疲力尽。为了让它们享受集市，FJ 安排了一辆穿梭卡车在集市场地内接送奶牛。

FJ 无法租到一辆非常好的穿梭车，所以他租的穿梭车只沿着它的路线行驶一次，并在路径上停靠 $N$（$1\leq N\leq2\times10^4$）个站点（编号为 $1\dots N$）。总共有 $K$（$1\leq K\leq5\times10^4$）组奶牛（编号为 $1\dots K$）希望使用穿梭车，每组 $i$ 中的 $M_i$（$1\leq M_i\leq N$）头奶牛希望从一个站点 $S_i$（$1\leq S_i<E_i$）乘车到沿路线更远的另一个站点 $E_i$（$S_i<E_i\leq N$）。

穿梭车可能无法接载整组奶牛（因为它的容量有限），但可以根据需要接载部分奶牛。

给定穿梭卡车的容量 $C$（$1\leq C\leq100$）以及希望参观集市上各个地点的奶牛组的描述，确定在集市期间可以乘坐穿梭车的奶牛的最大数量。

输入格式

第一行：包括三个整数：$K,N$ 和 $C$，彼此用空格隔开。

第二行到 $K+1$ 行：在第 $i+1$ 行，将会告诉你第 $i$ 组奶牛的信息：$S_i,E_i$ 和 $M_i$，彼此用空格隔开。

输出格式

第一行：可以坐班车的奶牛的最大头数。

8 15 3
1 5 2
13 14 1
5 8 3
8 14 2
14 15 1
9 12 1
12 15 2
4 6 1

10

提示

【样例说明】

班车可以把 $2$ 头奶牛从 $1$ 送到 $5$，$3$ 头奶牛从 $5$ 送到 $8$，$2$ 头奶牛从 $8$ 送到 $14$，$1$ 头奶牛从 $9$ 送到 $12$，$1$ 头奶牛从 $13$ 送到 $14$，$1$ 头奶牛从 $14$ 送到 $15$。 （由 ChatGPT 4o 翻译）