In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Byteasar works as a ticket inspector in a Byteotian National Railways (BNR)
express train that connects Byteburg with Bitwise.
The third stage of the BNR reform (The never ending saga of BNR reforms and the Bitwise hub was presented
in the problems Railway from the third stage of XIV Polish OI
and Station from the third stage of XV Polish OI. Their
knowledge, however, is not required at all in order to solve this
problem.) has begun. In particular, the salaries system has already been changed.
For example, to encourage Byteasar and other ticket inspectors to
efficient work,
their salaries now depend on the number of tickets (passengers) they
inspect. Byteasar is able to control all the passengers on the train in the
time between two successive stations, but he is not eager to waste his
energy in doing so. Eventually he decided he would check the tickets exactly
times per ride.
Before setting out, Byteasar is given a detailed summary from which he knows exactly how many passengers will travel from each station to another. Based on that he would like to choose the moments of control in such a way that the number of passengers checked is maximal. Obviously, Byteasar is not paid extra for checking someone multiple times - that would be pointless, and would only disturb the passengers. Write a programme that will determine for Byteasar when he should check the tickets in order to maximise his revenue.
In the first line of the standard input two positive integers and
(
,
) are given. These are separated by a
single space and denote, respectively, the number of stations en route and
the number of controls Byteasar intends to make. The stations are numbered
from
to
in the order of appearance on the route.
In the next lines the summary on passengers is given. The
-th
line contains information on the passengers who enter the train on the
station
- it is a sequence of
nonnegative integers
separated by single spaces. The number
(for
) denotes the number of passengers who
enter the train on station
and leave it on station
. The total
number of passengers (i.e. the sum of all
) does not exceed
.
Your programme should print out (in a single line) an increasing sequence
of integers from the interval from
to
separated by single
spaces to the standard output. These numbers should be the numbers of
stations upon leaving which Byteasar should control the tickets.
For the input data:
7 2 2 1 8 2 1 0 3 5 1 0 1 3 1 2 2 3 5 6 3 2 1
the correct result is:
2 5
or
3 5
In both cases Byteasar controls 42 tickets.
Task author: Marcin Kubica.