题目描述

有一条拥有$m$家商店的商店街，商店从左至右编号依次为 $1...m$。

有 $n$ 个客户慕名前来购买一款商品，该商品在每家商店中的定价暂未确定。其中第 $i$ 名客户在浏览商店街时会经过第 $l_i$ 家商店到第 $r_i$ 家商店中的所有商店，且他对这件商品的最高预算为 $p_i$，如果他经过的店中，最便宜的一家商品价格小于或等于 $p_i$，客户 $i$ 就会购买商品，反之则不会。

请你为每家商店的商品制定一个价格，使得所有商家的总收入之和达到最高。

输入格式

输入第一行，两个正整数 $n,m$ 接下来 $n$ 行，每行三个正整数 $l_i,r_i,p_i$

输出格式

输出共一行，表示给每家商店定价后，整条商店街的最大总收入。

4 6
1 4 10
2 4 6
1 2 12
3 6 9

31

样例解释 1

商店从左至右定价分别为12,12,10,10,9,9元 顾客1消费10元，顾客2不消费，顾客3消费12元，顾客4消费9元 故商店节总收入31元。

数据范围

• 对于 $30\%$ 的数据，$1\leq n,m \leq 10$
• 对于 $60\%$ 的数据，$1\leq n \leq 100, 1 \leq m \leq 20$
• 对于 $100\%$ 的数据，$1\leq n \leq 1000,1\leq m\leq 50$,$1 \leq l_i,r_i \leq m,1 \leq p_i \leq 10^6$