HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50688 - Epoka Furgon

Guest
• Review clarifications (1)

Section problems

• 50673 - DNA Testing
• 50997 - Dynamic Knights
• 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

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

Question: Epoka university bus service company has decided to grow. They bought several furgons and started service from Tirana to all around Albania. There are several stations (k) on the road and each bus has m seats. There are several different pricing according to the number of stations travelling.

  • 60 leke for one station
  • 80 leke for two or three stations
  • 100 leke from 4 to 6 stations.
  • 200 leke for more stations.

Station ki has several people waiting for the bus. We know how many stations will each person go. Like, they are getting off after 3, 5, 2, 1, 2 stations etc. Because the driver cannot know the number of people on the following stations, if he has more seats than the number of people in the current station, he takes all. If there are less empty seats than the number of people in the station, to increase the profit, the driver takes the earliest getting off people first.

Question: Write a program that gets the number of stations (k) and the number of seats (c) in the bus. Then, your program should read the people information waiting in the stations and calculate the money gathered on that journey.

Input specification
You will be given two integers first number (c and k) where 0 ≤ c ≤ 1,000 and 0 ≤ k ≤ 30,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.

Output specification
Show one number: the total amount of money gathered in that journey.

 Sample Input   
 6 4
 3 4 2 1 -1
 2 2 1 3 -1
 2 2 1 1 1 1 -2
 1 1 -1
 Sample Output   
 780


Для отправки решений необходимо выполнить вход.

www.contester.ru