매트

매트 회사에서 세로 폭이 $W$미터이고 가로로 긴 매트 원판을 만들었다. 원판은 너무 커서 그대로 팔지 못하므로, 작은 조각으로 재단해서 판다. 이 회사가 가진 재단 기계는 구형이라 다음 제약이 있다.

1. 변의 길이가 정수인 직사각형 조각으로만 재단한다.
2. 원판의 가로 변에 평행하거나 수직인 방향으로만 자른다.
3. 재단한 조각은 원판의 윗변과 아랫변 중 하나에 반드시 닿아 있다. 양쪽 변에 모두 닿아 있어도 된다.
4. 원판의 가로 변에는 1미터마다 눈금이 매겨져 있고, 세로 방향으로는 눈금 위치, 즉 정수 미터 위치에서만 자를 수 있다.

원판에는 아이들이 좋아하는 캐릭터가 그려져 있고, 캐릭터마다 선호도가 달라서 조각을 팔아 얻는 이익도 다르다. 회사는 시장조사로 어느 부분을 재단해 팔면 얼마를 버는지 미리 파악했다. 위 그림은 상품이 되는, 즉 이익을 얻을 수 있는 조각의 모양을 표시한 예다. 아랫변에 닿아 있는 조각은 파란색, 윗변에 닿아 있는 조각은 붉은색으로 그렸다.

조각 하나는 왼쪽 변의 위치 $L$, 오른쪽 변의 위치 $R$, 세로변의 길이 $H$, 그리고 닿아 있는 변으로 정해진다. 윗변에 닿은 조각은 가로로 눈금 $L$부터 $R$까지, 세로로 윗변에서 $H$미터 내려온 곳까지를 차지한다. 아랫변에 닿은 조각은 가로로 눈금 $L$부터 $R$까지, 세로로 아랫변에서 $H$미터 올라간 곳까지를 차지한다.

회사는 재단한 조각을 팔아 얻는 이익의 합이 최대가 되도록 원판을 재단하려 한다. 직사각형 모양의 매트만 상품이 되므로 고른 조각들의 내부가 서로 겹치면 안 된다. 변만 겹치는 경우는 허용된다. 예를 들어 왼쪽 변이 눈금 7에 있는 붉은색 조각(그림에서 빗금 친 조각)을 잘라 상품으로 만들면, 왼쪽 변이 눈금 4에 있는 붉은색 조각과 왼쪽 변이 눈금 0에서 시작하는 파란색 조각은 상품이 되지 못한다. 하지만 왼쪽 변이 눈금 10에 있는 파란색 조각은 빗금 친 조각과 변만 닿으므로 함께 상품이 된다.

상품이 되는 조각의 위치 정보와 이익이 주어질 때, 원판을 재단해 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하시오.

첫째 줄에 상품이 되는 매트 조각의 개수를 나타내는 정수 $N$ ($3 \le N \le 3000$)과 원판의 세로 폭을 나타내는 정수 $W$ ($1 \le W \le 10^8$)가 주어진다.

다음 $N$개의 줄에는 조각 하나의 정보를 나타내는 정수 다섯 개 $P$, $L$, $R$, $H$, $K$가 주어진다. $P$는 조각이 원판의 어느 변에 닿아 있는지를 나타내며, 윗변에 닿아 있으면 0이고 아랫변에 닿아 있으면 1이다. 양쪽 변에 모두 닿아 있는 조각은 0과 1 중 하나가 임의로 주어진다. $L$과 $R$ ($0 \le L < R \le 10^8$)은 조각의 왼쪽 변과 오른쪽 변의 위치이고, $H$ ($1 \le H \le W$)는 조각의 세로변의 길이, $K$ ($1 \le K \le 10000$)는 그 조각을 팔아 얻는 이익이다.

매트 원판을 재단해 얻을 수 있는 이익의 최댓값을 정수 하나로 출력한다.