HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > IMPC-2014-15 Questions > problem:


4th-6. 50536 - Epoka Furgon Shpk

IMPC-2014-15 Questions

Start: Nov.22.2014 at 03:00:00 PM
Finish: Nov.22.2014 at 08:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 3rd-2. 50405 - Accounts Receivable
• 3rd-3. 50474 - Sum of Two Primes
• 3rd-4. 50406 - Draw Pattern 178
• 3rd-5. 50415 - The Scientist
• 3rd-6. 50695 - Longest link between...
• 4th-1. 50491 - Brokers
• 4th-2. 50524 - Elevator
• 4th-3. 50535 - Image Compression
• 4th-6. 50536 - Epoka Furgon Shpk
• Ind_01-10. 50752 - Student Groups
• Ind_01-20. 50416 - Placing Domino...
• Ind_01-30. 50764 - Fast Typing Co...
• Ind_01-50. 50718 - Elevator
• Ind_02-10. 50497 - Falling Bricks - ...
• Ind_02-20. 50745 - Bitonic Sequence
• Ind_02-30. 50657 - Permutations an...
• Ind_03-10. 50743 - Total Scholarshi...

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.

Epoka Furgon Shpk

The government wants to give better service to his people. Prime minister has ordered the public transportation directorate to build a new transportation system. Because “Epoka Furgon” sh.p.k has grown bigger and got experience, now they want to get this contract from the government.

There are several stations (k) on the way, the train has m seats. Station ki has several people waiting for the train. And the ticket sellers know how many stations each person will travel, like passenger pi is getting off after si stations. And thus, the government wants to maximize the number of people using the service.

Question: Write a program that gets the number of stations (k) and the number of seats (c) in the train. Then, your program will read the people information waiting in the stations and calculate the maximum number of people that can be served in one journey.

Input specification
You will be given two integers first number (k and c) where 0 ≤ k ≤ 2,000 and 0 ≤ c ≤ 1,000. Each of the following k lines will have an unknown number of number ending with a negative number. The numbers in each line are between 1 and k. And, there can be at most 5,000 people.

Output specification
Show one number: the maximum number of people that can travel in this journey.

Sample Input I
4 6
3 4 2 1 -1
2 2 1 3 -1
2 2 1 1 1 1 -2
1 1 -1
Sample Output I
11

Explanation:
Here are the ID's of the people who get on the bus
  0 2 3 4 5 6 10 11 12 14 15


3 is the ID of the 4th person in the first bus station who will get off after one station.
10 is the ID of the 3rd person in the third station who will get off after one station, etc.



Äëÿ îòïðàâêè ðåøåíèé íåîáõîäèìî âûïîëíèòü âõîä.

www.contester.ru