14131413 SUSTech Online Judge
Problem 1413 --Coin Collector

## 1413: Coin Collector

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 120  Solved: 24
[Submit][Status][Web Board]

## Description

To celebrate the 10th anniversary of SUSTech, coins are falling from the heaven! $$Bob$$ is on the way to collect them. Now there are some coins. The coin with index $$i$$ will arrive in the ground at $$t_i$$ second and at $$x_i$$ position, value of which is $$y_i$$. If at $$t_i$$ second $$Bob$$ is exactly at $$x_i$$ position, he can collect that coin. In addition, each coin is so magical that only if $$Bob$$ collect the coin with index $$j$$ last time, which is less or equal than $$r_i(j \leq r_i)$$, can he collect the coin with index $$i$$. Particularly, $$Bob$$ can immediately collect the FIRST coin by ignoring this magic. Meanwhile, it's known that if $$t_i > t_j$$, then there will be $$x_i \geq x_j$$. It's guarantee that if $$t_i = t_j$$, there will not be $$x_i = x_j$$.
At the beginning, $$Bob$$ can start at any position he wants. Each second, $$Bob$$ can move to $$x_i + 1$$ or $$x_i - 1$$ if he is now at $$x_i$$. He wants to maximize the sum of the values of all coins he collects. Can you tell him?

## Input

The first line contains an integer $$n$$ indicating the total number of coins.
Next $$n$$ lines, each line consists of four integers $$t_i,x_i,y_i,r_i$$, describing the information of each coin.
$$1\leq n \leq 10^5$$, $$1 \leq t_i,x_i,y_i \leq 10^9$$, $$1 \leq r_i \leq n$$.

## Output

In a single line, print out the answer representing the max sum of the value $$Bob$$ can get.

## Sample Input

5
1 1 1 5
2 2 1 5
5 4 1 5
4 4 2 5
3 2 5 1

## Sample Output

7

[Submit][Status]