Kezdőlap


Feladat:	S.134	Korcsoport: -	Nehézségi fok: -
Füzet:	2019/április, 232. oldal		PDF \| MathML

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Szeretnénk új könyveket venni. Egy boltban $N$ féle könyvet árusítanak, az $i$ -ediket $P_{i}$ forintért. Szerencsére rendelkezünk $K$ darab kuponnal. Ha az $i$ -edik könyv megvételekor elhasználunk egy kupont, akkor azt $P_{i}$ helyett $R_{i}$ forintért tudjuk megvásárolni. Egy könyvnél csak egy kupont tudunk elhasználni. Adjuk meg, hogy legföljebb hány könyvet tudunk megvásárolni $M$ forintért.

A standard bemenet első sora tartalmazza az

N

K

M

számokat; a következő

N

darab sor tartalmazza a

P_{i}

és

R_{i}

számokat. A kimeneten adjuk meg, hogy legfeljebb hány könyvet tudunk megvenni.

Példa:

\begin{matrix} Bemenet(a/jel sortörést helyettesít) & Kimenet \\ 4 1 7 & 3 \\ 3 2 / 2 2 / 8 1 / 4 3 \end{matrix}

Korlátok:

1 \leq K \leq N \leq 50 000

1 \leq M \leq 10^{14}

1 \leq R_{i} \leq P_{i} \leq 10^{9}

. Időlimit: 0,5 mp.

Beküldendő egy s134.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztő környezetben futtatható.