Valentine's Day '15 P2 - Simon and Marcy

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M
Author:
bobhob314
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 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).

Input Specification

  • 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.

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 of 5 princesses wooed.

Comments