## Simon and Marcy

View as PDF

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type
##### 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 cages lined up next to each other numbered from to , with princesses in each cage, such that . 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 () songs to cage , with each song being 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 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).

#### Input Specification

• First line: , (, )
• Lines to : (space-separated), in order from cage to .

#### Output Specification

The maximum number of princesses that could be satisfied, i.e. have all the songs played to them.

#### Sample Input

4 10
2 5
4 7
3 10
1 1

#### Sample Output

5

#### Explanation

Wooing cage #2 satisfies 4 princesses, taking 7 minutes, leaving one minute to woo cage #4 for a grand total for 5 princesses wooed.

• puppy  commented on Nov. 13, 2019, 8:48 p.m.

Why is everybody here a weeb?

• p1geon  commented on Nov. 16, 2019, 9:44 p.m.

adventure time isn't even an anime?

• Raymo111  commented on Oct. 1, 2018, 12:23 p.m. edit 2

Input specification should be "Lines to ", not "Lines to "

• Rimuru  commented on Oct. 1, 2018, 12:42 p.m.

Fixed it.

• bobhob314  commented on March 8, 2015, 2:02 p.m.
• nullptr  commented on Feb. 14, 2015, 9:40 a.m.

There are no constraints on N_i

• quantum  commented on Feb. 14, 2015, 12:40 p.m.

Fixed.