직사각형 안의 직사각형

Bobo에게는 왼쪽 아래 꼭짓점이 $(0, 0)$이고 오른쪽 위 꼭짓점이 $(w, 10^6)$인 큰 직사각형이 있다. 또한 큰 직사각형 안에 축에 평행한 작은 직사각형 $n$개가 있다. $i$번째 직사각형의 가중치는 $v\_i$이다. 각 직사각형은 왼쪽 변 또는 오른쪽 변 중 하나만(둘 다는 아님) 큰 직사각형의 왼쪽 변이나 오른쪽 변과 일치한다.

Bobo는 작은 직사각형의 부분집합을 고르려고 한다. 이때 직사각형들은 서로 닿을 수는 있지만 겹치면 안 된다. 즉, 둘 이상의 직사각형 내부에 속하는 점이 있어서는 안 된다. Bobo는 가능한 모든 경우 중에서 가중치 합이 최대가 되는 경우를 원한다.

입력은 0개 이상의 테스트 케이스로 이루어지며, 파일의 끝에서 종료된다. 각 테스트 케이스는 다음과 같다.

첫째 줄에는 정수 $n$과 $w$가 주어진다. ($1 \leq n \leq 2000$, $2 \leq w \leq 10^6$) $n$은 작은 직사각형의 개수이고 $w$는 큰 직사각형의 너비이다.

다음 $n$개 줄 중 $i$번째 줄에는 정수 다섯 개 $\mathit{type}\_i$, $l\_i$, $a\_i$, $b\_i$, $v\_i$가 주어진다. ($\mathit{type}\_i \in \{0, 1\}$, $0 \leq a\_i < b\_i \leq 10^6$, $1 \leq l\_i < w$, $0 \leq v\_i \leq 10^6$) 여기서 $v\_i$는 $i$번째 직사각형의 가중치이다. $\mathit{type}\_i = 0$이면 $i$번째 직사각형의 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점이 각각 $(0, a\_i)$와 $(l\_i, b\_i)$이고, $\mathit{type}\_i = 1$이면 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점이 각각 $(w - l\_i, a\_i)$와 $(w, b\_i)$이다.

모든 $1 \leq i < j \leq n$에 대해 $a\_i \ne a\_j$, $a\_i \ne b\_j$, $b\_i \ne a\_j$, $b\_i \ne b\_j$임이 보장된다. 또한 모든 $n$의 합은 $2000$을 넘지 않는다.

각 테스트 케이스마다 가중치 합의 최댓값을 나타내는 정수를 한 줄에 출력한다.

세 번째 테스트에서 Bobo는 3번째, 4번째, 5번째 직사각형을 고를 수 있다.