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.
Äëÿ îòïðàâêè ðåøåíèé íåîáõîäèìî âûïîëíèòü âõîä.
|