408845: GYM103348 G Ophelia's Flowers

When the world is falling apart around her, Ophelia finds comfort in flowers and the powerful meaning possessed by each one. In fact, she likes to grow flowers in her garden and give them to her dearest friends as gifts.

Ophelia has decided to plant a new garden, in which she wants to grow $$$N$$$ unique flowers. She knows that each flower $$$f_i$$$ takes $$$d_i$$$ days to grow from a seed into a mature plant that Ophelia can then harvest and give away. So if she plants all $$$N$$$ flowers starting on the same day, it will take $$$\max\{d_1,...,d_N\}$$$ days for all of the flowers Ophelia planted to have finished maturing. However, Ophelia recently got her hands on $$$F$$$ pounds of Super-Gro medieval flower fertilizer, where each pound of fertilizer, when applied to a flower, shortens the growth time for that flower by a single day. Of course, it takes any flower at least a day to fully grow, so the Super-Gro fertilizer can't shorten the growth time below one day.

Help Ophelia grow all of her flowers as quickly as possible! If she plants the seeds for all $$$N$$$ flowers starting on the same day and makes good use of her fertilizer, what is the shortest number of days that it will take for all of Ophelia's flowers to reach maturity?

The first line of input contains an integer $$$N$$$ $$$(1 \leq N \leq 10^5)$$$, denoting the number of unique flowers Ophelia wants to plant. $$$N$$$ lines follow, each containing the unique name (consisting of all upper-case letters and no spaces) of the $$$i^{th}$$$ flower $$$f_i$$$, followed by an integer $$$d_i$$$ $$$(1 \leq d_i \leq 10^6)$$$ which is the number of days it will take for the flower $$$f_i$$$ to mature.

After those lines, the last line of input contains a single integer $$$F$$$ $$$(0 \leq F \leq 10^{12})$$$ which is the number of pounds of fertilizer Ophelia can use to accelerate the growth of her plants.

Output a single integer that is the minimum number of days it will take for Ophelia's flowers to all reach maturity.

7
ROSEMARY 10
PANSY 14
FENNEL 7
COLUMBINE 12
RUE 6
DAISY 7
VIOLET 3
37

4

Ophelia can achieve an optimal growth time of $$$4$$$ days in this example by using $$$6$$$ lbs of fertilizer on the rosemary, $$$10$$$ on the pansy, $$$3$$$ on the fennel, $$$8$$$ on the columbine, $$$2$$$ on the rue, $$$3$$$ on the daisy, and $$$0$$$ on the violet. This uses only $$$32$$$ out of her $$$37$$$ pounds of fertilizer.