题目描述

某趟列车的最大载客容量为$\red{V}$人，沿途共有$\red{n}$个停靠站，其中始发站为第$\red{1}$站，终点站为第$\red{n}$站。在第$\red{1}$站至第$\red{n-1}$站之间，共有$\red{m}$个团队申请购票搭乘，若规定：

$\red{（1)}$对于某个团队的购票申请，要么全部满足，要么全部拒绝，即不允许只满足部分。

$\red{（2）}$每个乘客的搭乘费用为其所乘站数。问：应如何选择这些购票申请，能使该趟列车获得最大的搭乘费用？其中，每个团队的购票申请格式是以空格分隔的三个整数：$\red{a ~ b~ t}$，即表示有$\red{t}$个人需要从第$\red{a}$站点乘至第$\red{b}$站点（注：每个团队的所有人员都必须同时在$\red{a}$站上车，且必须同时在后面的$\red{b}$站下车）。

输入格式

输入有若干行。第$\red{1}$行只有三个整数$\red{n，m，v}$，分别表示站点数、申请数、列车的最大载客容量。这三个整数之间都以一个空格分隔。第$\red{2}$行至第$\red{m+1}$行，每行有三个整数，中间都以一个空格分隔。其中第$\red{k+1}$行的三个整数$\red{a，b，t}$表示第$\red{k}$个申请，含义为：有$\red{t}$个人需要从第$\red{a}$站乘至第$\red{b}$站。其中：$\red{1≤n≤10}$；$\red{1≤m≤18}$

输出格式

输出只有一行，该行只有一个整数，该列车能获得的最大搭乘费用

样例

输入样例

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

输出样例

8