using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("3");
WillReturn.Add("2 3");
WillReturn.Add("11 2");
WillReturn.Add("4 5");
//6
}
else if (InputPattern == "Input2") {
WillReturn.Add("6");
WillReturn.Add("4 1");
WillReturn.Add("1 5");
WillReturn.Add("10 3");
WillReturn.Add("9 1");
WillReturn.Add("4 2");
WillReturn.Add("5 3");
//7
}
else if (InputPattern == "Input3") {
WillReturn.Add("15");
WillReturn.Add("1543361732 260774320");
WillReturn.Add("2089759661 257198921");
WillReturn.Add("1555665663 389548466");
WillReturn.Add("4133306295 296394520");
WillReturn.Add("2596448427 301103944");
WillReturn.Add("1701413087 274491541");
WillReturn.Add("2347488426 912791996");
WillReturn.Add("2133012079 444074242");
WillReturn.Add("2659886224 656957044");
WillReturn.Add("1345396764 259870638");
WillReturn.Add("2671164286 233246973");
WillReturn.Add("2791812672 585862344");
WillReturn.Add("2996614635 91065315");
WillReturn.Add("971304780 488995617");
WillReturn.Add("1523452673 988137562");
//4232545716
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static long[] GetSplitArr(string pStr)
{
return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
}
struct ItemInfoDef
{
internal long Weight;
internal long Score;
}
static List<ItemInfoDef> mItemInfoList = new List<ItemInfoDef>();
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = { };
Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);
foreach (string EachStr in InputList.Skip(1)) {
SplitAct(EachStr);
ItemInfoDef WillAdd;
WillAdd.Weight = wkArr[0];
WillAdd.Score = wkArr[1];
mItemInfoList.Add(WillAdd);
}
mItemInfoList = mItemInfoList.OrderBy(pX => pX.Weight).ToList();
int UB = mItemInfoList.Count - 1;
// 重さの階差数列
long[] KaisaArr = new long[mItemInfoList.Count];
for (int I = 1; I <= UB; I++) {
KaisaArr[I] = mItemInfoList[I].Weight - mItemInfoList[I - 1].Weight;
// マイナスをかけておく
KaisaArr[I] *= -1;
}
// 累積和1(階差数列)
long[] RunSumArr1 = (long[])KaisaArr.Clone();
for (int I = 0; I <= UB; I++) {
if (I > 0) {
RunSumArr1[I] += RunSumArr1[I - 1];
}
}
// 累積和2(スコア)
long[] RunSumArr2 = new long[mItemInfoList.Count];
for (int I = 0; I <= UB; I++) {
RunSumArr2[I] = mItemInfoList[I].Score;
if (I > 0) {
RunSumArr2[I] += RunSumArr2[I - 1];
}
}
var InsLazySegmentTree = new LazySegmentTree(UB, 0);
for (long I = 0; I <= UB; I++) {
InsLazySegmentTree.Internal_RangeAdd(I, I, RunSumArr1[I] + RunSumArr2[I]);
}
long Answer = long.MinValue;
for (int I = 0; I <= UB; I++) {
long AnswerKouho = InsLazySegmentTree.Internal_Query(I, UB);
Answer = Math.Max(Answer, AnswerKouho);
// 差分更新
if (I < UB) {
long AddVal = -(mItemInfoList[I].Score + KaisaArr[I + 1]);
InsLazySegmentTree.Internal_RangeAdd(I + 1, UB, AddVal);
}
}
Console.WriteLine(Answer);
}
}
#region LazySegmentTree
// LazySegmentTreeクラス (RMaxQ and RAQ)
internal class LazySegmentTree
{
private long[] mTreeNodeArr;
private long UB; // 木のノードの配列のUB
private long mLeafCnt; // 葉ノードの数
private long mExternalArrUB;
private long[] mLazyArr; // 遅延配列
// ノードの添字を引数とし、範囲の開始添字と終了添字を持つ配列
private struct RangeInfoDef
{
internal long StaInd;
internal long EndInd;
}
private RangeInfoDef[] mRangeInfo;
// ノードのIndexの列挙を返す
internal IEnumerable<long> GetNodeIndEnum()
{
for (long I = 0; I <= mExternalArrUB; I++) {
yield return I;
}
}
// 木のノードのUBを返す
internal long GetUB()
{
return mExternalArrUB;
}
// コンストラクタ
internal LazySegmentTree(long pExternalArrUB, long pInitVal)
{
mExternalArrUB = pExternalArrUB;
// 簡単のため、葉ノード数を2のべき乗に
long ArrLength = 0;
for (long I = 1; I < long.MaxValue; I *= 2) {
ArrLength += I;
mLeafCnt = I;
if (pExternalArrUB + 1 < mLeafCnt) break;
}
// すべての値をpInitValに
UB = ArrLength - 1;
mTreeNodeArr = new long[UB + 1];
for (int I = 0; I <= UB; I++) {
mTreeNodeArr[I] = pInitVal;
}
// 遅延配列を初期化
mLazyArr = new long[UB + 1];
// ノードの添字を引数とし、範囲の開始添字と終了添字を持つ配列の作成
mRangeInfo = new RangeInfoDef[UB + 1];
for (long I = 0; I <= UB; I++) {
if (I == 0) {
RangeInfoDef WillSet1;
WillSet1.StaInd = 0;
WillSet1.EndInd = mLeafCnt - 1;
mRangeInfo[I] = WillSet1;
continue;
}
long ParentNode = DeriveParentNode(I);
RangeInfoDef ParentRangeInfo = mRangeInfo[ParentNode];
RangeInfoDef WillSet2;
long Mid = (ParentRangeInfo.StaInd + ParentRangeInfo.EndInd) / 2;
if (I % 2 == 1) { // 奇数ノードの場合
WillSet2.StaInd = ParentRangeInfo.StaInd;
WillSet2.EndInd = Mid;
}
else { // 偶数ノードの場合
WillSet2.StaInd = Mid + 1;
WillSet2.EndInd = ParentRangeInfo.EndInd;
}
mRangeInfo[I] = WillSet2;
}
}
// 親ノードの添字を取得
private long DeriveParentNode(long pTarget)
{
return (pTarget - 1) / 2;
}
// 子ノードの添字(小さいほう)を取得
private long DeriveChildNode(long pTarget)
{
return pTarget * 2 + 1;
}
// 開始添字と終了添字とカレントノードを引数として、区間加算を行う
internal void Internal_RangeAdd(long pSearchStaInd, long pSearchEndInd, long pAddVal)
{
Private_RangeAdd(pSearchStaInd, pSearchEndInd, pAddVal, 0);
}
private void Private_RangeAdd(long pSearchStaInd, long pSearchEndInd, long pAddVal, long pCurrNode)
{
// カレントノードの遅延評価を行う
LazyEval(pCurrNode);
long CurrNodeStaInd = mRangeInfo[pCurrNode].StaInd;
long CurrNodeEndInd = mRangeInfo[pCurrNode].EndInd;
// OverLapしてなければ、何もしない
if (CurrNodeEndInd < pSearchStaInd || pSearchEndInd < CurrNodeStaInd)
return;
// 完全に含んでいれば、遅延配列に値を入れた後に評価
if (pSearchStaInd <= CurrNodeStaInd && CurrNodeEndInd <= pSearchEndInd) {
mLazyArr[pCurrNode] += pAddVal;
LazyEval(pCurrNode);
return;
}
// そうでなければ、2つの区間に再帰呼出し
long ChildNode1 = DeriveChildNode(pCurrNode);
long ChildNode2 = ChildNode1 + 1;
Private_RangeAdd(pSearchStaInd, pSearchEndInd, pAddVal, ChildNode1);
Private_RangeAdd(pSearchStaInd, pSearchEndInd, pAddVal, ChildNode2);
// カレントノードの更新
mTreeNodeArr[pCurrNode] = Math.Max(mTreeNodeArr[ChildNode1], mTreeNodeArr[ChildNode2]);
}
// 開始添字と終了添字とカレントノードを引数として、最大値を返す
// 開始添字と終了添字とカレントノードを引数として、最大値を返す
internal long Internal_Query(long pSearchStaInd, long pSearchEndInd)
{
return Private_Query(pSearchStaInd, pSearchEndInd, 0);
}
private long Private_Query(long pSearchStaInd, long pSearchEndInd, long pCurrNode)
{
// 該当ノードを遅延評価する
LazyEval(pCurrNode);
long CurrNodeStaInd = mRangeInfo[pCurrNode].StaInd;
long CurrNodeEndInd = mRangeInfo[pCurrNode].EndInd;
// OverLapしてなければ、long.MinValue
if (CurrNodeEndInd < pSearchStaInd || pSearchEndInd < CurrNodeStaInd)
return long.MinValue;
// 完全に含んでいれば、このノードの値
if (pSearchStaInd <= CurrNodeStaInd && CurrNodeEndInd <= pSearchEndInd)
return mTreeNodeArr[pCurrNode];
// そうでなければ、2つの子の最大値
long ChildNode1 = DeriveChildNode(pCurrNode);
long ChildNode2 = ChildNode1 + 1;
long ChildVal1 = Private_Query(pSearchStaInd, pSearchEndInd, ChildNode1);
long ChildVal2 = Private_Query(pSearchStaInd, pSearchEndInd, ChildNode2);
return Math.Max(ChildVal1, ChildVal2);
}
// カレントノードを引数として、遅延評価を行う
private void LazyEval(long pCurrNode)
{
// 遅延配列が0なら何もしない
if (mLazyArr[pCurrNode] == 0) return;
// 遅延配列の値を設定する
mTreeNodeArr[pCurrNode] += mLazyArr[pCurrNode];
long ChildNode1 = DeriveChildNode(pCurrNode);
long ChildNode2 = ChildNode1 + 1;
if (ChildNode1 <= UB) mLazyArr[ChildNode1] += mLazyArr[pCurrNode];
if (ChildNode2 <= UB) mLazyArr[ChildNode2] += mLazyArr[pCurrNode];
// 伝播が終わったので、自ノードの遅延配列を空にする
mLazyArr[pCurrNode] = 0;
}
internal void DebugPrint()
{
for (long I = 0; I <= UB; I++) {
if (mLazyArr[I] > 0) {
Console.WriteLine("mTreeNodeArr[{0}] = {1} , mLazyArr[{0}] = {2}",
I, mTreeNodeArr[I], mLazyArr[I]);
}
else {
Console.WriteLine("mTreeNodeArr[{0}] = {1}", I, mTreeNodeArr[I]);
}
}
}
}
#endregion