АВТ
Language: Russian
English

Remote Training on Programming

Problems Online status Contests
News FAQ E-learning
For authors:
Register  ||  Login
 
Hello, Guest! Please login or register.

241. Homeworks

Time Limit: 1 seconds
Memory Limit:65536KB
Points:100
View Problem Statistics Submit Problem added Undefined

Петя очень не любит делать домашние задания. Поэтому он просит отличников из своего класса сделать их за него. За это он даёт им шоколадные конфеты. Так как папа Пети работает на шоколадной фабрике, то у Пети всегда много конфет.

Но отличники — капризные ребята. В разные дни они просят разное количество конфет за выполнение домашнего задания. Про каждого отличника в классе Петя знает, сколько конфет придётся ему дать в i-й день учёбы, чтобы тот сделал за него домашнее задание. Кроме того, каждый день делать домашнее задание за Петю согласится не каждый отличник. Про каждого отличника Петя знает, какое максимальное количество домашних заданий тот согласится сделать за него подряд.

Требуется написать программу, которая по информации о количестве конфет, которое отличники просят за свои услуги, а также о максимальном количестве дней подряд, которое каждый отличник готов делать домашнее задание за Петю, определяет, какое минимальное количество конфет требуется Пете, чтобы все домашние задания были за него сделаны.

Input

Первая строка входного файла содержит два числа: n — количество учебных дней подряд, в течение которых Петя хочет, чтобы за него отличники делали домашние задания, и m  количество отличников в классе у Пети (1 <= n <= 100, 2 <= m <= 100).

Вторая строка входного файла содержит m целых чисел ai (1 <= i <= m), задающих для каждого отличника максимальное количество заданий подряд, которое он согласен выполнить за Петю (1 <= ai <= n).

Следующие m строк содержат по n неотрицательных целых чисел, при этом j-е число i-й строки означает количество конфет, которое Пете придётся отдать i-му отличнику, чтобы он сделал за Петю домашнее задание в j-й день. Все эти числа не превышают 106. Числа в строках разделяются пробелами.

Output

На первой строке выходного файла выведите одно число — минимальное количество конфет, которое необходимо Пете. На второй строке выведите n целых чисел, каждое из которых определяет для каждого дня номер отличника, который должен решать домашнее задание за Петю в этот день.

Sample

stdin

stdout

5 2
2 2
1 3 6 4 1
5 2 3 1 1
9
1 1 2 2 1

 

 


View Problem Statistics Submit Problem discussion Author/source:
Problems from Contests and Camps / School olympiads and couses of Vologda region / All-Russian school olympiad, regioanl stage / Vologda Region School Olympiad 2005-2006 /
240. Hairdresser 241. 237. Various Strings
time generating 0.578 sec.
© Copyright VSU, AVT, Nosov D.A., Andrianov I.A.