시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 61 | 31 | 18 | 60.000% |
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 di woltów, a i-ta bateryjka ma napięcie bi 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 di, bi opisujące kolejne druty (0 ≤ di, bi ≤ 106).
W jedynej linijce powinna znaleźć się liczba całkowita oznaczająca maksymalna liczbę drutów tworzących kółko.
2 2 2 2 2
2