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

Egy boltban 1≤N≤10001 \leq N \leq 1000 árut lehet vásárolni. Ehhez 1≤P≤1091 \leq P \leq 10^9 pénz áll rendelkezésünkre. Minden terméknek van egy AiA_i ára, és egy HiH_i házhozszállítási költsége, így a teljes költség az i.i. árura Ai+HiA_i+H_i (nemnegatív egészek, AiA_i a feladat megkönnyítése miatt páros). Van egy kuponunk, amivel egy választott termék árát megfelezhetjük, azaz Ai2+Hi\frac{A_i}{2}+H_i-ért kaphatjuk meg, ha az i.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 NN-et és PP-t, majd a következő NN sorból az AiA_i, HiH_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.

Information
Identifier:
is3
Title:
2015. november
Time limit:
2000 ms
Memory limit:
64 MiB
Tags:
show
Task type:
batch

Submit solution
Beküldéshez lépj be vagy regisztrálj!