Decimation was a form of extreme military discipline used
in the Roman Army, when every tenth soldier was executed.
Do you think it is easy to work as a conductor in a tram? Persistent fare
dodgers always try to ride free of charge, and ticket inspectors fine without
remorse not only fare dodgers but also tram conductors because they don't cope
with their duties.
In the course of operation Fare Dodger 2008, which was carried out
recently by the Yekaterinburg Association of Ticket Inspectors, it turned out
that in every tram there was at least one fare dodger at the moment of
inspection. Chief Ticket Inspector of Yekaterinburg became furious and decided
to punish conductors. He ordered to line them up in a column and to fine every
tenth conductor a sum equal to an average conductor's salary.
Chief Fare Dodger of Yekaterinburg felt sorry for poor conductors and
decided to help them, because he knew that some of the conductors were good and
coped with their duties. Before conductors are fined, Chief Fare Dodger can
place into the column some of his friends, who are also fare dodgers. Chief
Ticket Inspector doesn't suspect this and will fine every person whose number
in the column is a multiple of 10 (the number of the first person in the
column is 1). Help Chief Fare Dodger to place his friends in the column so
that the total number of fined fare dodgers and good conductors be minimal.
The first line contains integers n (1 ≤
n ≤ 10000) and k (0 ≤ k ≤ 50) separated by
a space; they are the number of conductors in the column and the number of
Chief Fare Dodger's friends who are ready to help the conductors. The second
line consists of n symbols; the ith symbol is “1” if
the ith place in the column is initially occupied by a good conductor,
and “0” if the conductor is bad.
In the first line, output the minimal total number of
fined fare dodgers and good conductors. In the second line, output the number
m of fare dodgers that should be placed in the column, and then output
m integers, which are their numbers in the resulting column. The numbers
must be separated by a space.
2 5 12
Problem Author: Alexander Ipatov (idea — Stanislav Vasilyev)
Problem Source: The 12th Urals Collegiate Programing Championship, March 29, 2008