Вообще-то Дракон знал, чем сейчас интересуется Принц. В последнее время свои нечастые выходные Принц проводил на разных курсах и тренингах. Вот только Дракон не был уверен, что Принцессе стоит об этом сказать.
Принц решил, что ему недостаёт некоторых знаний и навыков. Он определил, что в первую очередь хочет приобрести знания и навыки в n сферах деятельности. Затем он выяснил, что существует m1, m2, ..., mn курсов и тренингов по каждой из интересующих его сфер деятельности. Принц внимательно изучил описания курсов и тренингов и составил таблицу, в которой элемент sij обозначает, на какую величину он может улучшить свои знания и навыки в сфере деятельности #i, если запишется на курс #j (j = 1, 2, ..., mi).
Принц полагает, что его базовые знания и навыки в этих сферах деятельности практически не отличаются от нуля. И он хочет развивать их гармонично. Наибольшей гармонии (по мнению Принца) он достигнет, если выберет по одному курсу для каждой сферы деятельности таким образом, чтобы разница между наибольшей и наименьшей величинами приобретённых знаний и навыков была минимально возможной.
Ваша задача — определить, на какие курсы следует записаться Принцу.
В первой строке содержится целое число n (1 ≤ n ≤ 200) — количество интересующих Принца сфер деятельности.
Во второй строке содержится n целых чисел m1, m2, ..., mn (1 ≤ mj ≤ 1000, j = 1, 2, ..., n) — количество курсов по каждой из сфер деятельности.
В следующих n строках содержатся величины sij (1 ≤ sij ≤ 109) — знания и навыки, которые Принц может приобрести на курсах. В первой из этих n строк содержатся величины s11, s12, ..., s1m1, во второй — величины s21, s22, ..., s2m2 и т.д.
Величины sij перечислены в порядке нумерации курсов для каждой из сфер деятельности.
В первой строке выведите целое число — минимально возможную разность между наибольшей и наименьшей величинами приобретённых знаний и навыков.
Во второй строке выведите n целых чисел — номера курсов, на которые следует записаться Принцу. Перечисляйте номера согласно порядку сфер деятельности.
Если существует несколько вариантов ответа — выведите любой.
2
2 3
4 3
3 1 2
0
2 1
4
3 5 4 5
8 7 15
3 10 4 8 5
4 4 4 5
1 2 12 8 9
3
2 5 4 4
| V (XVI) открытый командный студенческий чемпионат Поволжья по спортивному программированию |
|---|
| Закончено |
