// C++ program to implement Best First Search using priority
// queue
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, int> pi;

struct node {
    int next, c, d;
    node(int next, int c, int d) {
        this->next = next;
        this->c = c;
        this->d = d;
    }
};

vector<vector<node> > graph;

// Function for adding edges to graph
void addedge(int a, int b, int c, int d)
{
	graph[a-1].push_back(node(b-1, c, d));
	graph[b-1].push_back(node(a-1, c, d));
}

// Function For Implementing Best First Search
// Gives output path having lowest cost
long long dijkstra(int source, int target, int n)
{
    vector<bool> visited(n, false);
	
	// MIN HEAP priority queue
	priority_queue<pi, vector<pi>, greater<pi> > pq;
	// sorting in pq gets done by first value of pair
	pq.push(make_pair(0, source));

	while (!pq.empty()) {
		int x = pq.top().second;
		long long t = pq.top().first;
		// Displaying the path having lowest cost
        // cout << x << "," << t << ' ';
		pq.pop();
		
		if (visited[x])
		    continue;
		visited[x] = true;
		
		if (x == target)
			return t;

		for (node v: graph[x]) {
			if (!visited[v.next]) {
			    long long t_best = ceil(sqrt((double)v.d))-1;
			    if (t_best < t)
			        t_best = t;
			    long long t_next = t_best + (long long)v.c + floor((double)v.d / (t_best+1));
				pq.push(make_pair(t_next, v.next));
			}
		}
	}
	return -1;
}

// Driver code to test above methods
int main()
{
	int n, m;
	cin >> n >> m;
	
	graph.resize(n);
	
	int a, b, c, d;
	for (int i = 0; i < m; i++) {
	    cin >> a >> b >> c >> d;
	    addedge(a, b, c, d);
	}

	// Function call
	cout << dijkstra(0, n-1, n);

	return 0;
}

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
#define int long long
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 2e5 + 100;
int n, a[maxn], b[maxn],res;
signed main()
{
    read(n);
    long long now = 0;
    for (int i = 1; i <= n; ++i) read(a[i]),read(b[i]),now -= a[i],a[i] = b[i] + 2 * a[i];
    std::sort(a + 1,a + 1 + n);
    for(int i = n;i;--i)
    {
        if (now > 0) { printf("%lld\n", res); return 0; }
        now += a[i], ++res;
    }
    printf("%lld\n", res);
    return 0;
}