Mat

A mat company produced a mat roll that is $W$ meters tall and long in the horizontal direction. The roll is too large to sell as it is, so the company cuts it into smaller pieces and sells those. The cutting machine the company owns is an old model and works under the following restrictions.

1. It cuts only rectangular pieces whose side lengths are integers.
2. It cuts only in a direction parallel or perpendicular to the horizontal edge of the roll.
3. Every piece that is cut out touches the top edge or the bottom edge of the roll. Touching both edges is allowed.
4. The horizontal edge of the roll is marked every 1 meter, and a vertical cut is possible only at a mark, that is, at an integer position.

Characters that children like are printed on the roll. Each character has a different popularity, so the profit from selling a piece differs from piece to piece. Market research told the company in advance how much it earns by cutting out and selling each part. The picture above shows an example of the pieces that can be sold, that is, the pieces that bring a profit. Pieces touching the bottom edge are drawn in blue and pieces touching the top edge are drawn in red.

One piece is determined by the position $L$ of its left edge, the position $R$ of its right edge, the length $H$ of its vertical side, and the edge it touches. A piece touching the top edge covers the horizontal range from mark $L$ to mark $R$, and vertically the band from the top edge down to $H$ meters below it. A piece touching the bottom edge covers the horizontal range from mark $L$ to mark $R$, and vertically the band from the bottom edge up to $H$ meters above it.

The company wants to cut the roll so that the total profit of the pieces it sells is as large as possible. Only rectangular mats can be sold, so the interiors of the chosen pieces must not overlap. Overlapping along edges only is allowed. For example, if the red piece whose left edge sits at mark 7 (the hatched piece in the picture) is cut out and sold, then the red piece whose left edge sits at mark 4 and the blue piece that starts at mark 0 cannot be sold. The blue piece whose left edge sits at mark 10 touches the hatched piece along an edge only, so it can be sold together with it.

Given the position and the profit of every piece that can be sold, write a program that computes the maximum profit obtainable by cutting the roll.

The first line contains an integer $N$ ($3 \le N \le 3000$), the number of mat pieces that can be sold, and an integer $W$ ($1 \le W \le 10^8$), the height of the roll.

Each of the next $N$ lines contains five integers $P$, $L$, $R$, $H$, $K$ describing one piece. $P$ tells which edge of the roll the piece touches: it is 0 if the piece touches the top edge and 1 if it touches the bottom edge. For a piece that touches both edges, either 0 or 1 is given arbitrarily. $L$ and $R$ ($0 \le L < R \le 10^8$) are the positions of the left edge and the right edge of the piece, $H$ ($1 \le H \le W$) is the length of its vertical side, and $K$ ($1 \le K \le 10000$) is the profit obtained by selling it.

Print one integer, the maximum profit obtainable by cutting the mat roll.