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

HINT

Source

 

[Submit][Status]