يوجد إجمالاً $N + 1$ نوعاً من الطعام: $N$ أنواع من الطعام مرقمة بـ $1, 2, \dots, N$، وهلام الماء. لكل $i = 1, 2, \dots, N$، حلاوة الطعام $i$ هي $A_i$ وحرارته (توابلُه) هي $B_i$. حلاوة هلام الماء هي $0$ وحرارته هي $0$.

يأكل UTPC-kun أولاً هلام الماء، ثم يأكل الأطعمة $1, 2, \dots, N$ مرة واحدة بالضبط لكل منها بأي ترتيب، وأخيراً يأكل هلام الماء مرة أخرى.

تكون سعادة UTPC-kun مساوية لـ $0$ مباشرة بعد تناول هلام الماء الأول. بعد ذلك، في كل مرة يأكل فيها طعاماً، تتغير سعادته على النحو التالي:

• ليكن $a$ و $b$ حلاوة وحرارة الطعام الذي يأكله حالياً، وليكن $a'$ و $b'$ حلاوة وحرارة الطعام الذي أكله قبله مباشرة. تزداد سعادته بمقدار $\max(a - a', b - b')$. (يمكن أن تكون الزيادة في السعادة سالبة.)

أوجد أقصى سعادة نهائية ممكنة لـ UTPC-kun عن طريق اختيار الترتيب الأمثل لتناول الأطعمة $1, 2, \dots, N$.

الإدخال

يُعطى الإدخال بالصيغة التالية:

N
A_1 B_1
A_2 B_2
:
A_N B_N

• جميع قيم الإدخال هي أعداد صحيحة.
• $1 \le N \le 5 \times 10^5$
• $0 \le A_i, B_i \le 10^9$

الإخراج

اطبع الإجابة في سطر واحد.

أمثلة

مثال الإدخال 1

4
1 4
3 1
2 3
3 4

مثال الإخراج 1

6

مثال الإدخال 2

3
1 2
2 1
1 2

مثال الإخراج 2

3

مثال الإدخال 3

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

مثال الإخراج 3

18

ملاحظة

في المثال الأول، أحد الترتيبات المثلى لتناول الأطعمة هو $1, 2, 3, 4$. في هذه الحالة، تتغير سعادة UTPC-kun كما يلي بعد انتهائه من تناول هلام الماء الأول:

• يأكل الطعام $1$: تزداد سعادته بمقدار $\max(1 - 0, 4 - 0) = 4$، لتصبح $4$.
• يأكل الطعام $2$: تزداد سعادته بمقدار $\max(3 - 1, 1 - 4) = 2$، لتصبح $6$.
• يأكل الطعام $3$: تزداد سعادته بمقدار $\max(2 - 3, 3 - 1) = 2$، لتصبح $8$.
• يأكل الطعام $4$: تزداد سعادته بمقدار $\max(3 - 2, 4 - 3) = 1$، لتصبح $9$.
• يأكل هلام الماء: تزداد سعادته بمقدار $\max(0 - 3, 0 - 4) = -3$، لتصبح $6$.