Triển lãm bò

Cho \(n\) con bò, con bò thứ \(i\) có chỉ số IQ là \(a_i\) và EQ là \(b_i\). Bạn muốn mang một số con bò đi triển lãm (có thể không mang con nào) sao cho tổng toàn bộ IQ và EQ của chúng là lớn nhất, đồng thời tổng riêng biệt IQ và EQ của chúng không được nhỏ hơn \(0\).

Input

• Dòng đầu tiên gồm số nguyên \(n\) (\(1 \le n \le 500\)).

• \(n\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(a_i, b_i\) (\(|a_i|, |b_i| \le 1000\)).

Output

In ra một số nguyên là tổng toàn bộ IQ và EQ của những con bò lớn nhất có thể.

Example

Input:

5
-5 7
8 -6
6 -3
2 1
-8 -5

Output:

8

Note

Lấy con bò thứ \(1\), \(3\), và \(4\).

Lấy thêm con bò thứ \(2\) sẽ cho kết quả là \(10\) nhưng sẽ khiến tổng EQ âm.