전시회

승원이는 미술품 $N$개를 가지고 있다. 미술품에는 1번부터 $N$번까지 번호가 매겨져 있고, $i$번 미술품의 크기는 $A_i$, 가치는 $B_i$이다.

오늘 승원이는 저택 1층에서 미술품을 전시하려고 한다. 전시할 미술품은 다음 조건에 맞게 고른다.

• 전시할 미술품 중 가장 큰 크기를 $A_{max}$, 가장 작은 크기를 $A_{min}$, 전시할 미술품의 가치의 합을 $S$라고 한다.
• 이때 $S - (A_{max} - A_{min})$이 가장 커야 한다.

미술품은 적어도 하나 전시한다. 미술품 $N$개의 크기와 가치가 주어질 때, $S - (A_{max} - A_{min})$의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 미술품의 개수 $N$ ($2 \le N \le 500{,}000$)이 주어진다.

둘째 줄부터 $N$개의 줄에 1번 미술품부터 순서대로 미술품의 크기 $A_i$와 가치 $B_i$가 주어진다. ($1 \le A_i \le 1{,}000{,}000{,}000{,}000{,}000 = 10^{15}$, $1 \le B_i \le 1{,}000{,}000{,}000$)

첫째 줄에 $S - (A_{max} - A_{min})$의 최댓값을 출력한다.

첫 번째 예제에서 승원이는 미술품 3개를 가지고 있고, 크기와 가치는 다음과 같다.

• 1번 미술품의 크기는 2, 가치는 3이다.
• 2번 미술품의 크기는 11, 가치는 2이다.
• 3번 미술품의 크기는 4, 가치는 5이다.

1번과 3번을 전시하면 $S - (A_{max} - A_{min}) = 6$이고, 이 값이 가장 크다.

• 크기가 가장 큰 미술품은 3번이므로 $A_{max} = 4$이다.
• 크기가 가장 작은 미술품은 1번이므로 $A_{min} = 2$이다.
• 전시할 미술품의 가치의 합은 $3 + 5 = 8$이다.

따라서 $S = 8$이고 $S - (A_{max} - A_{min})$은 6이다.