Apple Catching

문제

It's raining apples! At certain points in time, some number of apples will hit the number line. At certain points in time, some of Farmer John's cows will arrive on the number line and start catching apples.

If an apple hits the number line without a cow to catch it, it is lost forever. If a cow and an apple arrive at the same time, the cow catches it. Each cow can travel one unit per second. Once a cow catches a single apple, she exits the number line.

If FJ's cows collaborate optimally, how many apples can they catch in total?

입력

The first line contains $NN$ ($1\le N\le 2\cdot {10}^{5}1\backslash le\; N\backslash le\; 2\backslash cdot\; 10^5$), the number of times apples hit the number line or FJ's cows appear.

The next $NN$ lines each contain four integers $q_{i}q\_i$, $t_{i}t\_i$, $x_{i}x\_i$, and $n_{i}n\_i$ ($q_i\in \{1,2\},0\le t_i\le {10}^9,0\le x_i\le {10}^9,1\le n_i\le {10}^{3}q\_i\backslash in\; \backslash \{1,2\backslash \},\; 0\backslash le\; t\_i\backslash le\; 10^9,\; 0\backslash le\; x\_i\backslash le\; 10^9,\; 1\backslash le\; n\_i\backslash le\; 10^3$).

 

• If $q_i=1q\_i=1$, this means that $n_{i}n\_i$ of FJ's cows arrive on the number line at time $t_{i}t\_i$ at location $x_{i}x\_i$.
• If $q_i=2q\_i=2$, this means that $n_{i}n\_i$ apples will hit the number line at time $t_{i}t\_i$ at location $x_{i}x\_i$.

It is guaranteed that all of the ordered pairs $(t_i,x_i)(t\_i,x\_i)$ are distinct.

출력

The maximum number of apples FJ's cows may collectively catch.

5
2 5 10 100
2 6 0 3
2 8 10 7
1 2 4 5
1 4 7 6

10

5
2 5 10 100
2 6 0 3
2 8 11 7
1 2 4 5
1 4 7 6

9