Vasya got really tired of these credits (from problem F) and now wants to earn the money himself! He decided to make a contest to gain a profit.

Vasya has n problems to choose from. They are numbered from 1 to n. The difficulty of the i-th problem is d_i. Moreover, the problems are given in the increasing order by their difficulties. The difficulties of all tasks are pairwise distinct. In order to add the i-th problem to the contest you need to pay c_i burles to its author. For each problem in the contest Vasya gets a burles.

In order to create a contest he needs to choose a consecutive subsegment of tasks.

So the total earnings for the contest are calculated as follows: 

  * if Vasya takes problem i to the contest, he needs to pay c_i to its author; 
  * for each problem in the contest Vasya gets a burles; 
  * let gap(l, r) = max_{l ≤ i < r} (d_{i + 1} - d_i)^2. If Vasya takes all the tasks with indices from l to r to the contest, he also needs to pay gap(l, r). If l = r then gap(l, r) = 0. 



Calculate the maximum profit that Vasya can earn by taking a consecutive segment of tasks.

Input

The first line contains two integers n and a (1 ≤ n ≤ 3 ⋅ 10^5, 1 ≤ a ≤ 10^9) — the number of proposed tasks and the profit for a single problem, respectively.

Each of the next n lines contains two integers d_i and c_i (1 ≤ d_i, c_i ≤ 10^9, d_i < d_{i+1}).

Output

Print one integer — maximum amount of burles Vasya can earn.

Examples

Input


5 10
1 15
5 3
6 11
7 2
11 22


Output


13


Input


3 5
1 8
2 19
3 11


Output


0
import java.lang.*;
import java.math.*;
import java.util.*;
import java.io.*;

public class Main {
    void solve() {
        int n=ni(),A=ni();
        a=new long[n+1];
        long [] b=new long[n+1];
        pref=new long[n+1];
        long d[]=new long[n+1];
        for(int i=1;i<=n;i++) {
            d[i]=nl(); a[i]=A-nl();
            pref[i]=pref[i-1]+a[i];
        }
        for(int i=1;i<n;i++) b[i]=(d[i+1]-d[i])*(d[i+1]-d[i]);
        if(n==1){
            pw.println(a[1]>0?a[1]:"0");
            return;
        }
        tree=new long[4*n+1][2];
        build(1,1,n);
        int st[]=new int[n+1];
        int ed[]=new int[n+1];
        st[1]=-1;
        for(int i=2;i<=n;i++){
            int id=i-1;
            while(id!=-1 && b[id]<b[i]){
                id=st[id];
            }
            st[i]=id;
        }
        ed[n]=-1;
        for(int i=n-1;i>=1;i--){
            int id=i+1;
            while(id!=-1 && b[id]<=b[i]){
                id=ed[id];
            }
            ed[i]=id;
        }
//        for(int i=1;i<=n;i++){
//            long sm=0,mx=Long.MIN_VALUE;
//            sm+=a[i];
//          //  if(a[i]==0)pw.println(i);
//            for(int j=i+1;j<=n;j++){
//                sm+=a[j];
//                mx=Math.max(mx,b[j-1]);
//                if(sm-mx==0) pw.println(i+" "+j);
//            }
//
//
//        }

        long ans=0;
//        for(int i=1;i<=n;i++) pw.print(b[i]+" ");
//        pw.println("");
//        for(int i=1;i<=n;i++) pw.print(pref[i]+" ");
//
//        pw.println("");
//        pw.println("");
        for(int i=1;i<n;i++){
            int l=st[i],r=ed[i];
            if(l==-1) l=1; else l++;
            if(r==-1) r=n;
            long mx=queryMX(1,i,r,1,n),mn=-1;
            if(l>1)mn=queryMN(1,l-1,i-1,1,n);
            else {
                mn=queryMN(1,l,i-1,1,n);
                mn=Math.min(mn,0);
            }

            ans=Math.max(ans,mx-mn-b[i]);

           // pw.println(i+" "+l+" "+r+" "+(mx-mn-b[i])+" "+mx+" "+mn+" "+b[i]);
            ans=Math.max(ans,a[i]);
            if(ans==-3) pw.println(i);

        }
        ans=Math.max(ans,a[n]);
        pw.println(ans);

    }
    long a[];
    long tree[][];
    long pref[];
    void build(int id,int l,int r){
        if(l==r){
            tree[id][0]=tree[id][1]=pref[l];
        }else {
            int mid=(l+r)>>1;
            build(2*id,l,mid);
            build(2*id+1,mid+1,r);
            tree[id][0]=Math.max(tree[2*id][0],tree[2*id+1][0]);
            tree[id][1]=Math.min(tree[2*id][1],tree[2*id+1][1]);

        }
    }
    long queryMX(int id,int x,int y,int l,int r){
        if(r<x || l>y) return Long.MIN_VALUE;
        if(x<=l && r<=y) return tree[id][0];
        int mid=(l+r)>>1;
        return Math.max(queryMX(2*id,x,y,l,mid),queryMX(2*id+1,x,y,mid+1,r));
    }
    long queryMN(int id,int x,int y,int l,int r){
        if(x>y) return 0;
        if(r<x || l>y) return Long.MAX_VALUE;
        if(x<=l && r<=y) return tree[id][1];
        int mid=(l+r)>>1;
        return Math.min(queryMN(2*id,x,y,l,mid),queryMN(2*id+1,x,y,mid+1,r));
    }


    long M = (long) 1e9 + 7;
    InputStream is;
    PrintWriter pw;
    String INPUT = "";

    void run() throws Exception {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        pw = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        pw.flush();
        if (!INPUT.isEmpty()) tr(System.currentTimeMillis() - s + "ms");

    }

    public static void main(String[] args) throws Exception {
        new Main().run();
    }

    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;

    private int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {
                lenbuf = is.read(inbuf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (lenbuf <= 0) return -1;
        }
        return inbuf[ptrbuf++];
    }

    private boolean isSpaceChar(int c) {
        return !(c >= 33 && c <= 126);
    }

    private int skip() {
        int b;
        while ((b = readByte()) != -1 && isSpaceChar(b)) ;
        return b;
    }

    private double nd() {
        return Double.parseDouble(ns());
    }

    private char nc() {
        return (char) skip();
    }

    private String ns() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[] ns(int n) {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) {
            buf[p++] = (char) b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private char[][] nm(int n, int m) {
        char[][] map = new char[n][];
        for (int i = 0; i < n; i++) map[i] = ns(m);
        return map;
    }

    private int[] na(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = ni();
        return a;
    }

    private int ni() {
        int num = 0, b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }

        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private long nl() {
        long num = 0;
        int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }

        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

    private void tr(Object... o) {
        if (INPUT.length() > 0) System.out.println(Arrays.deepToString(o));
    }

}