Valentine's Day '15 P2 - Simon and Marcy - DMOJ: Modern Online Judge

Valentine's Day '15 P2 - Simon and Marcy

View as PDF

Submit solution

All submissions

Best submissions

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$ $C$ cages lined up next to each other numbered from $1$ $1$ to $C$ $C$ , with $N_i$ $N_{i}$ princesses in each cage, such that $N_i < 1\,000$ $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}$ ( $K_i < 1\,000$ $K_{i} < 1 000$ ) songs to cage $i$ $i$ , with each song being $1$ $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$ $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$ $C$ , $M$ $M$ ( $1 \le C \le 10^3$ $1 \leq C \leq 10^{3}$ , $1 \le M \le 10^3$ $1 \leq M \leq 10^{3}$ )
Lines $2$ $2$ to $C+1$ $C + 1$ : $N_i$ $N_{i}$ $K_i$ $K_{i}$ (space-separated), in order from cage $1$ $1$ to $C$ $C$ .

Output Specification

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

Sample Input

Copy

Sample Output

Copy

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

4

tortle commented on Jan. 12, 2022, 2:25 a.m.

it's 2022 and this is still the best problem on this site

-13

puppy commented on Nov. 14, 2019, 1:48 a.m.

Why is everybody here a weeb?

This comment is hidden due to too much negative feedback. Show it anyway.

11

p1geon commented on Nov. 17, 2019, 2:44 a.m.

adventure time isn't even an anime?

12

bobhob314 commented on March 8, 2015, 6:02 p.m.

http://fc09.deviantart.net/fs71/i/2013/089/8/6/simon_and_marcy_by_fauxboy-d5zve4u.png