2015. november
time limit per test
2000 ms
memory limit per test
64 MiB
input
stdin
output
stdout

Egy boltban \(1 \leq N \leq 1000\) árut lehet vásárolni. Ehhez \(1 \leq P \leq 10^9\) pénz áll rendelkezésünkre. Minden terméknek van egy \(A_i\) ára, és egy \(H_i\) házhozszállítási költsége, így a teljes költség az \(i.\) árura \(A_i+H_i\) (nemnegatív egészek, \(A_i\) a feladat megkönnyítése miatt páros). Van egy kuponunk, amivel egy választott termék árát megfelezhetjük, azaz \(\frac{A_i}{2}+H_i\)-é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 \(A_i\), \(H_i\) 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
Copy
5 24
4 2
2 0
8 1
6 3
12 5
Output
Copy
4

Notes

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
Tagek:
show
Típus:
batch

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


Mellékletek