题目内容

小红在玩一款模拟经营游戏，这个游戏按时间排序有$n$个事件，每个事件可以在两种选项种选择一种：

$(1)$消耗$x$颗宝石，获得$y$枚金币。

$(2)$获得$z$颗宝石。

不过，宝石的数量是有上限的，在任何时刻，若小红的宝石数量大于$m$，则大于$m$部分的宝石直接消失。

在$n$个事件结束后，小红每拥有$1$颗宝石，都可以将其换成$1$枚金币。

小红初始时没有宝石，他想知道，在最优策略下，他最多可以获得多少金币

输入描述

第一行输入两个整数 $n,m(1≤n,m≤1000)$表示事件个数和宝石上限。

接下来$n$行，每行输入三个整数

$x,y,z(1≤x,y,z≤10^9)$,表示每一个事件。

输出描述

输出一个整数表示答案。

样例1

输入

3 3
1 2 1
1 3 1
1 2 4

输出

6

说明

第$1$个事件，小红选择选项$2$，获得$1$颗宝石。

第$2$个事件，小红选择选项$1$,消耗$1$颗宝石，获得$3$枚金币。

第$3$个事件，小红选择选项$1$,获得$4$颗宝石，但由于宝石数量上限为$3$，因此小红只有$3$颗宝石。

最后，小红将$3$颗宝石换成$3$枚金币。

因此答案为$6$。