19427번 - Rectangles Inside Rectangle 다국어

문제

Bobo has a large rectangle with lower left and upper right corners at $(0, 0)$ and $(w, 10^6)$. He also has $n$ small axis-parallel rectangles inside the large rectangle. The weight of the $i$-th rectangle is $v_i$. For each rectangle, either its left border or its right border (but not both) coincides with the left or right side of the large rectangle.

Bobo would like to choose a subset of small rectangles in such a manner that the rectangles may touch each other, but they do not overlap (that is, there are no points that belong to the interior of more than one rectangle). Among all the possibilities, he wants the one with the maximum possible sum of weights.

입력

The input contains zero or more test cases, and is terminated by end-of-file. For each test case:

The first line contains two integers $n$ and $w$ (1ドル \leq n \leq 2000,ドル 2ドル \leq w \leq 10^6$) denoting the number of small rectangles and the width of the large rectangle.

The $i$-th of the following $n$ lines contains five integers $\mathit{type}_i,ドル $l_i,ドル $a_i,ドル $b_i$ and $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$) where $v_i$ is the weight of the $i$-th rectangle. Here, $\mathit{type}_i = 0$ means the lower left and upper right corner of the $i$-th rectangle are $(0, a_i)$ and $(l_i, b_i),ドル while $\mathit{type}_i = 1$ means the lower left and upper right corner of the $i$-th rectangle are $(w - l_i, a_i)$ and $(w, b_i)$.

It is guaranteed that for all 1ドル \leq i < j \leq n,ドル $a_i \ne a_j,ドル $a_i \ne b_j,ドル $b_i \ne a_j$ and $b_i \ne b_j$. Additionally, the sum of all $n$ does not exceed 2000ドル$.

출력

For each test case, output an integer which denotes the maximum sum of weights.

제한

힌트

For the third test, Bobo can choose the 3ドル$-rd, 4ドル$-th and 5ドル$-th rectangles.