P13649 [NOISG 2016] Panda Ski

The Winter Olympics is coming and Mr. Panda has been training very hard to take part in the skiing event. This event takes place on the mountain Mt. Rar which is of height $H$. Everyone can ski down from the peak to the base using the centroid path. To increase the difficulties, $N$ gates, each associated with a score, are placed at various heights and either to the left or to the right of the centroid path. The objective is to ski down from the peak to the base and achieve score by passing through some subset of gates. The $i$-th gate is located at height $Y_i$ and $X_i$ units to the right of the centroid path. If $X_i$ is negative then it is to the left of the centroid path. Passing through the $i$-th gate gives $S_i$ points and you can pass through the same gate multiple times but you only get points for the first time you pass through a gate. No gate is at the same point. Mr. Panda wants to maximize his score. Moreover, Mr. Panda understands he is not a good skier and he will fail to visit some gates. To avoid embarrassing himself, Mr. Panda analyses the gates and gives each gate an easiness score $E_i$ (high score is easier) based on the angle of the slope, the amount of snow, etc. Precisely, Mr. Panda calculated that he can move from the $i$-th gate to the $j$-th gate if $\max(|X_j - X_i|, Y_i - Y_j) \leq E_i$ and $Y_i \geq Y_j$. Also, it is possible to get from the peak to any gate and from any gate to the base of the mountain. Mr. Panda is overwhelmed by the number of possible paths moving down the mountain and he needs your help to find the path that will give him the maximum score.

Your program must read from standard input. The first line of input contains two positive integers $N$ and $H$. The next $N$ lines contain 4 integers each. The $(i+1)$-th line represents $X_i, Y_i, S_i, E_i$.

You program must output one line with a single integer to the standard output, which is the maximum score Mr. Panda can attain.

### Explanation There are only 3 possible paths Mr. Panda can take. 1. Top $\rightarrow (0, 5) \rightarrow$ Bottom, Score: 5 2. Top $\rightarrow (3, 4) \rightarrow (1, 1) \rightarrow$ Bottom, Score: $4 + 4 = 8$ 3. Top $\rightarrow (-2, 3) \rightarrow (-1, 2) \rightarrow$ Bottom, Score: $3 + 3 = 6$ So the best score is 8. ### Subtasks The maximum execution time on each instance is 1.0s. Your program will be tested on sets of input instances as follows: | Subtask | Marks | $N$ | Others | | :-: | :-: | :-: | :-: | | 1 | 7 | $1 \leq N \leq 300$ | $E_i = 200000$ for all $i$ | | 2 | 8 | $1 \leq N \leq 300$ | $X_i = 0$ for all $i$, $E_i = E_j$ for all $i, j$ | | 3 | 11 | $1 \leq N \leq 300$ | $Y_i \neq Y_j$ for all $i \neq j$ | | 4 | 13 | $1 \leq N \leq 2000$ | $Y_i \neq Y_j$ for all $i \neq j$ | | 5 | 15 | $1 \leq N \leq 50000$ | $Y_i \neq Y_j$ for all $i \neq j$, $E_i = E_j$ for all $i, j$ | | 6 | 13 | $1 \leq N \leq 50000$ | $E_i = E_j$ for all $i, j$ | | 7 | 16 | $1 \leq N \leq 50000$ | $Y_i \neq Y_j$ for all $i \neq j$ | | 8 | 17 | $1 \leq N \leq 200000$ | $Y_i \neq Y_j$ for all $i \neq j$ | For all test cases, $-50000 \leq X_i \leq 50000$, $1 \leq Y_i \leq H \leq 200000$, $1 \leq S_i \leq 10^6$, $1 \leq E_i \leq 200000$