The only difference between easy and hard versions is that you should complete all the projects in easy version but this is not necessary in hard version.

Polycarp is a very famous freelancer. His current rating is r units.

Some very rich customers asked him to complete some projects for their companies. To complete the i-th project, Polycarp needs to have at least a_i units of rating; after he completes this project, his rating will change by b_i (his rating will increase or decrease by b_i) (b_i can be positive or negative). Polycarp's rating should not fall below zero because then people won't trust such a low rated freelancer.

Is it possible to complete all the projects? Formally, write a program to check if such an order of the projects exists, that Polycarp has enough rating before starting each project, and he has non-negative rating after completing each project.

In other words, you have to check that there exists such an order of projects in which Polycarp will complete them, so he has enough rating before starting each project, and has non-negative rating after completing each project.

Input

The first line of the input contains two integers n and r (1 ≤ n ≤ 100, 1 ≤ r ≤ 30000) — the number of projects and the initial rating of Polycarp, respectively.

The next n lines contain projects, one per line. The i-th project is represented as a pair of integers a_i and b_i (1 ≤ a_i ≤ 30000, -300 ≤ b_i ≤ 300) — the rating required to complete the i-th project and the rating change after the project completion.

Output

Print "YES" or "NO".

Examples

Input


3 4
4 6
10 -2
8 -1


Output


YES


Input


3 5
4 -5
4 -2
1 3


Output


YES


Input


4 4
5 2
5 -3
2 1
4 -2


Output


YES


Input


3 10
10 0
10 -10
30 0


Output


NO

Note

In the first example, the possible order is: 1, 2, 3.

In the second example, the possible order is: 2, 3, 1.

In the third example, the possible order is: 3, 1, 4, 2.
import java.io.*;
import java.util.*;
import java.math.*;

public class codefForces {
    static Scanner sc = new Scanner(System.in);
    static PrintWriter pw = new PrintWriter(System.out), pw2 = new PrintWriter(System.out);
    static int n,r;
    static project[] arr;
    static class project implements Comparable<project>{
        int req,bonus;
        project(int req,int bonus){
            this.req=req;
            this.bonus=bonus;
        }

        @Override
        public String toString() {
            return req+" "+bonus;
        }

        @Override
        public int compareTo(project o) {
            return req==o.req?0:req-o.req;
        }
    }
    public static void main(String[] args) throws IOException {
        n=sc.nextInt();r=sc.nextInt();
        ArrayList<project> pos=new ArrayList<>();
        ArrayList<project> neg=new ArrayList<>();
        for(int i=0;i<n;i++){
            int req=sc.nextInt(),bonus=sc.nextInt();
            if(bonus<0){
                neg.add(new project(req,bonus));
            }else{
                pos.add(new project(req,bonus));
            }
        }
        Collections.sort(pos);
        for(int i=0;i<pos.size();i++){
            if(pos.get(i).req>r){
                System.out.println("NO");
                return;
            }else{
                r+=pos.get(i).bonus;
            }
        }
        Collections.sort(neg, new Comparator<project>() {
            @Override
            public int compare(project a, project b) {
                return (a.bonus + a.req) ==(b.bonus+b.req)?0:(b.bonus+b.req)-(a.bonus+a.req);
            }
        });
        for(int i=0;i<neg.size();i++){
            if(r<neg.get(i).req){
                System.out.println("NO");
                return;
            }else{
                r+=neg.get(i).bonus;
            }
        }
        System.out.println(r>=0?"YES":"NO");
    }

    public static <E> void print2D(E[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                pw.println(arr[i][j]);
            }
        }
    }

    public static int digitSum(String s) {
        int toReturn = 0;
        for (int i = 0; i < s.length(); i++) toReturn += Integer.parseInt(s.charAt(i) + " ");
        return toReturn;
    }

    public static boolean isPrime(long n) {
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;

        if (n % 2 == 0 || n % 3 == 0)
            return false;

        for (long i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
        return true;
    }

    public static long pow(long a, long pow) {
        return pow == 0 ? 1 : pow % 2 == 0 ? pow(a * a, pow >> 1) : a * pow(a * a, pow >> 1);
    }

    public static long sumNum(long a) {
        return a * (a + 1) / 2;
    }

    public static int gcd(int n1, int n2) {
        return n2 == 0 ? n1 : gcd(n2, n1 % n2);
    }

    public static long factorial(long a) {
        return a == 0 || a == 1 ? 1 : a * factorial(a - 1);
    }

    public static Double[] solveQuadratic(double a, double b, double c) {
        double result = (b * b) - 4.0 * a * c;
        double r1;
        if (result > 0.0) {
            r1 = ((double) (-b) + Math.pow(result, 0.5)) / (2.0 * a);
            double r2 = ((double) (-b) - Math.pow(result, 0.5)) / (2.0 * a);
            return new Double[]{r1, r2};
        } else if (result == 0.0) {
            r1 = (double) (-b) / (2.0 * a);
            return new Double[]{r1, r1};
        } else {
            return new Double[]{null, null};
        }
    }

    public static BigDecimal[] solveQuadraticBigDicimal(double aa, double bb, double cc) {
        BigDecimal a = BigDecimal.valueOf(aa), b = BigDecimal.valueOf(bb), c = BigDecimal.valueOf(cc);
        BigDecimal result = (b.multiply(b)).multiply(BigDecimal.valueOf(4).multiply(a.multiply(c)));
        BigDecimal r1;
        if (result.compareTo(BigDecimal.ZERO) > 0) {
            r1 = (b.negate().add(bigSqrt(result)).divide(a.multiply(BigDecimal.valueOf(2))));
            BigDecimal r2 = (b.negate().subtract(bigSqrt(result)).divide(a.multiply(BigDecimal.valueOf(2))));
            return new BigDecimal[]{r1, r2};
        } else if (result.compareTo(BigDecimal.ZERO) == 0) {
            r1 = b.negate().divide(a.multiply(BigDecimal.valueOf(2)));
            return new BigDecimal[]{r1, r1};
        } else {
            return new BigDecimal[]{null, null};
        }
    }

    private static BigDecimal sqrtNewtonRaphson(BigDecimal c, BigDecimal xn, BigDecimal precision) {
        BigDecimal fx = xn.pow(2).add(c.negate());
        BigDecimal fpx = xn.multiply(new BigDecimal(2));
        BigDecimal xn1 = fx.divide(fpx, 2 * BigDecimal.valueOf(16).intValue(), RoundingMode.HALF_DOWN);
        xn1 = xn.add(xn1.negate());
        BigDecimal currentSquare = xn1.pow(2);
        BigDecimal currentPrecision = currentSquare.subtract(c);
        currentPrecision = currentPrecision.abs();
        if (currentPrecision.compareTo(precision) <= -1) {
            return xn1;
        }
        return sqrtNewtonRaphson(c, xn1, precision);
    }

    public static BigDecimal bigSqrt(BigDecimal c) {
        return sqrtNewtonRaphson(c, new BigDecimal(1), new BigDecimal(1).divide(BigDecimal.valueOf(10).pow(16)));
    }

    static class graph {
        int V;
        ArrayList<Integer> adjL[];
        boolean vis[];

        public graph(int V) {
            this.V = V;
            adjL = new ArrayList[V + 1];
            vis = new boolean[V + 1];
            for (int i = 0; i < V + 1; i++) adjL[i] = new ArrayList<>();
        }

        public void addEdge(int v1, int v2) {
            this.adjL[v1].add(v2);
        }

        public void BFS(int n) {
            Queue<Integer> q = new LinkedList<>();
            q.add(n);
            while (!q.isEmpty()) {
                int a = q.poll();
                vis[a] = true;
                for (int x : adjL[a]) {
                    if (!vis[x]) {
                        vis[x] = true;
                        q.add(x);
                    }
                }
            }
        }

        public void DFS(int v) {
            vis[v] = true;
            for (int u : adjL[v]) {
                if (!vis[u]) {
                    DFS(u);
                }
            }
        }

        public void DFS(int v, Stack<Integer> st) {
            vis[v] = true;
            for (int u : adjL[v]) {
                if (!vis[u]) {
                    DFS(u, st);
                }
            }
            st.push(v);
        }
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            String x = next();
            StringBuilder sb = new StringBuilder("0");
            double res = 0, f = 1;
            boolean dec = false, neg = false;
            int start = 0;
            if (x.charAt(0) == '-') {
                neg = true;
                start++;
            }
            for (int i = start; i < x.length(); i++)
                if (x.charAt(i) == '.') {
                    res = Long.parseLong(sb.toString());
                    sb = new StringBuilder("0");
                    dec = true;
                } else {
                    sb.append(x.charAt(i));
                    if (dec)
                        f *= 10;
                }
            res += Long.parseLong(sb.toString()) / f;
            return res * (neg ? -1 : 1);
        }

        public boolean ready() throws IOException {
            return br.ready();
        }
    }

    static class pair<E1, E2> implements Comparable<pair> {
        E1 x;
        E2 y;

        pair(E1 x, E2 y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(pair o) {
            return x.equals(o.x) ? (Integer) y - (Integer) o.y : (Integer) x - (Integer) o.x;
        }

        @Override
        public String toString() {
            return x + " " + y;
        }

        public double pointDis(pair p1) {
            return Math.sqrt(((Integer) y - (Integer) p1.y) * ((Integer) y - (Integer) p1.y) + ((Integer) x - (Integer) p1.x) * ((Integer) x - (Integer) p1.x));
        }
    }

}
