Valentine's Day 2015 Contest
For whatever reason, the princesses say that they don't want to hear the #1 BABE sing his songs or read his PwP fanfiction out loud anymore! In fact, they say that they want to be home so they can pre-order Marceline's new CD, The Morning Will Wait For Us. Luckily, the Ice King is a babe and therefore is one of Marceline's best friends. He calls Marceline on his ice phone so she can "ice" the bad atmosphere in the ice room (made of ice).
To the surprise of the princesses, Marceline actually arrives, with her ax base in tow. When she enters the room she finds ~C~ cages lined up next to each other numbered from ~1~ to ~C~, with ~N_i~ princesses in each cage, such that ~N_i < 1\,000~. She's not really into wooing princesses, but she can't help but help the Ice King. They've had history together.
To the surprise of the Ice King, everyone is into Marceline and each cage of princesses asks her to play ~K_i~ (~K_i < 1\,000~) songs to cage ~i~, with each song being ~1~ minute in length. Marceline complies, but she doesn't want to be there forever (there are a sizeable number of princesses). She will only stay for ~M~ minutes. She wants to know the maximum number of princesses she could satisfy. Since she can float, it takes her no time to travel between cages (made of ice).
- First line: ~C~, ~M~ (~1 \le C \le 10^3~, ~1 \le M \le 10^3~)
- Lines ~2~ to ~C+1~: ~N_i~ ~K_i~ (space-separated), in order from cage ~1~ to ~C~.
The maximum number of princesses that could be satisfied, i.e. have all the songs played to them.
4 10 2 5 4 7 3 10 1 1
Wooing cage #2 satisfies 4 princesses, taking 7 minutes, leaving one minute to woo cage #4 for a grand total of 5 princesses wooed.