409076: GYM103430 I Tetris

Monocarp is playing a modified version of Tetris game.

The game field is a rectangle divided into square cells. The rectangle contains $$$k$$$ rows (numbered $$$1$$$ through $$$k$$$ from bottom to top) and $$$10^9 + 1$$$ columns (numbered $$$0$$$ through $$$10^9$$$ from left to right). Initially, all cells are empty.

Initially, Monocarp's score in the game is $$$0$$$. To increase it, Monocarp can drop tetris pieces onto the game field. Each tetris piece is a rectangle with a certain width and a height equal to $$$1$$$. When the $$$i$$$-th piece appears on the game field, it initially occupies the cells from $$$l_i$$$ to $$$r_i$$$ (inclusive) in the $$$k$$$-th row of the field. After that, the piece starts falling: it moves one row down (i. e. stops occupying the cells in the current row and starts occupying the cells in the row right below the current one) until it either reaches the row $$$1$$$, or at least one of the cells directly below the piece is already occupied. Formally, if the piece is currently occupying the cells $$$[l_i, r_i]$$$ in the $$$j$$$-th row, it stops if and only if one of the following conditions is met:

• $$$j = 1$$$;
• at least one of the cells from $$$l_i$$$-th to $$$r_i$$$-th in the $$$(j-1)$$$-th row is already occupied.

Each tetris piece falls vertically downward, Monocarp cannot force them to move left or right (as it is possible in regular Tetris). While a tetris piece is falling, Monocarp cannot drop any new tetris pieces, he must wait until the current piece stops falling.

Monocarp can drop up to $$$n$$$ tetris pieces onto the game field. If the $$$i$$$-th piece is dropped, it initially occupies the cells from $$$l_i$$$ to $$$r_i$$$ in the $$$k$$$-th row (and if at least one of those cells is already occupied, the piece cannot be dropped); and dropping it increases Monocarp's score by $$$c_i$$$. Monocarp can drop any tetris pieces in any order, but each tetris piece can be dropped at most once.

What is the maximum possible score Monocarp can achieve?

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 5000$$$; $$$1 \le k \le \min(n, 10)$$$).

Then $$$n$$$ lines follow, the $$$i$$$-th line contains three integers $$$l_i$$$, $$$r_i$$$ and $$$c_i$$$ ($$$0 \le l_i \le r_i \le 10^9$$$; $$$0 \le c_i \le 10^9$$$) — the description of the $$$i$$$-th tetris piece.

Print one integer — the maximum possible score Monocarp can achieve.

4 2
0 3 30
0 1 5
2 3 10
1 2 14

45

4 2
0 3 30
0 1 5
2 3 10
1 2 16

46

4 3
0 3 10
1 4 7
2 5 3
3 6 20

37

You can see the explanations for the examples in the following picture: