HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50536 - Epoka Furgon Shpk

Guest
• Review clarifications (1)

Section problems

• 50936 - Saving the Soldiers
• 50979 - Minimum access cost for BST
• 51062 - Fish Pond II
• 51010 - Max Sequential Sum
• 51072 - Castle on chessboard
• 51075 - Shortest Path for Bishop
• 50688 - Epoka Furgon
• 50524 - Elevator
• 50536 - Epoka Furgon Shpk
• 50687 - Pascal Triangle - 2
• 50689 - The biggest building block
• 50686 - The Container
• 50682 - Hotel Durres
• 50930 - Tom and Jerry
• 50526 - Gold Market
• 50488 - Connecting Wires
• 50681 - Center of a Series

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