8735번 - Obwody 다국어

문제

Jaś na urodziny dostał komplet magicznych elektrycznych kabelków. Każdy kabelek składa się z drutu oraz bateryjki. i-ty drut może wytrzymać napięcie d_i woltów, a i-ta bateryjka ma napięcie b_i woltów.

Jasio buduje z kabelków obwody: wybiera druty, skręca je razem tworząc grubszy drut i robi z niego kółko. W kółku napięcie jest sumą napięć wszystkich bateryjek, a skręcony drut może wytrzymać napięcie będące sumą napięć, które mogą wytrzymać poszczególne druty.

Jaś buduje obwód tak, aby zrobione kółko nie przepaliło się. Z ilu maksymalnie kabelków może się ono składać?

입력

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita n (1 ≤ n ≤ 500 000), oznaczająca liczę drutów. W n następnych linijkach pary liczb d_i, b_i opisujące kolejne druty (0 ≤ d_i, b_i ≤ 10⁶).

출력

W jedynej linijce powinna znaleźć się liczba całkowita oznaczająca maksymalna liczbę drutów tworzących kółko.

제한

힌트