题目描述

Bobo has a set P of n distinct points $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$.
The i-th point has two weights $a_i$ and $b_i$.
He wants to partition the points into two sets A and B (That is, $A \cup B = P$ and $A \cap B = \emptyset$.
A partition (A, B) is valid if and only if there exists no $i \in A$ and $j \in B$ where $x_i \geq x_j$​ and $y_i \leq y_j$.
Find the maximum of $ \left(\sum_{i \in A} a_i \right) + \left(\sum_{j \in B} b_j\right) $ among all valid partitions (A, B).

输入格式

The input consists of several test cases and is terminated by end-of-file.

The first line of each test cases contains an integer n. The i-th of the following n lines contains four integers $x_i, y_i, a_i, b_i$.

• $1 \leq n \leq 10^5$
• $1 \leq x_i, y_i, a_i, b_i \leq 10^9$
• $(x_i, y_i) \neq (x_j, y_j)$ for all $i \neq j$
• The sum of n does not exceed $5 \times 10^5$ .

输出格式

For each test case, print an integer which denotes the result.

样例

样例输入

2
1 2 1 9
2 1 9 1
1
1 1 2 3
4
1 1 1 5
1 2 2 6
2 1 3 7
2 2 4 8

样例输出

10
3
26