Books
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 337
Solved: 112
- Description
- Benjamin likes to read books. Benjamin likes books a lot. Ben's teacher knows this, so he likes to encourage Ben to read. At the start of the summer Ben's teacher offers a proposition to Ben. Let D be the number of days in summer. For each book Ben reads, his teacher will give him D-x points, where x is the day Ben finishes the book. Ben knows for each book he has how long it will take to read it, and if he starts a book he must finish it before starting a different book, but he can read the books in any order he chooses. Help Ben browse the books better!
- Input
- There will be several test cases.
Each test case will start with a positive integer D that is at most 100. Then several lines will follow representing the books. Each line will contain a single positive integer x which is how long it takes to read that particular book.
Between each test case there will be a blank line.
- Output
- For each test case output a line "Ben can earn P points!" where P is the highest possible number of points Ben can earn.
- sample input
-
10 7 5 5 10 2 2 2 100 12 57 23 72 38 17
- sample output
-
Ben can earn 5 points! Ben can earn 18 points! Ben can earn 217 points!
- hint
- During the first summer, Ben can either finish the 7 book, or he can finish both 5's. It turns out it's better to finish the 5's, the first one gives 10-5=5 points, while the last one gives 10-10=0 points (he might as well just not read the second book). During the second summer, it doesn't matter which order Ben reads the books, since they all take the same amount of time to read. He finishes the first book on day 2, so he gets 8 points for it. He finishes the second book on day 4, so he gets 6 points. And he gets 4 points for book 3. That is 18 points overall.
- source