2015. november
2015. november
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Egy boltban 1 ≤ N ≤ 1000 árut lehet vásárolni. Ehhez 1 ≤ P ≤ 109 pénz áll rendelkezésünkre. Minden terméknek van egy Ai ára, és egy Hi házhozszállítási költsége, így a teljes költség az i. árura Ai + Hi (nemnegatív egészek, Ai a feladat megkönnyítése miatt páros). Van egy kuponunk, amivel egy választott termék árát megfelezhetjük, azaz -ért kaphatjuk meg, ha az i. termékre használjuk fel. Adjuk meg, legfeljebb hány terméket tudunk megvásárolni a boltban, ha egyetlen kupont használhatunk fel.

A program olvassa be a standard input első sorából N-et és P-t, majd a következő N sorból az Ai, Hi szóközzel elválasztott egészeket, és írja a standard output első és egyetlen sorába maximálisan megvásárolható termékek számát.

Example

Input
5 24
4 2
2 0
8 1
6 3
12 5
Output
4

Note

Az első 4 terméket meg tudjuk venni, ha a 3.-ra használjuk fel a kupont.

Információk
Azonosító:
is3
Cím:
2015. november
Időlimit:
2000 ms
Memórialimit:
64 MiB
Típus:
batch

Megoldás beküldése
Beküldéshez lépj be vagy regisztrálj!

Mellékletek