I. Стремление к совершенству
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вообще-то Дракон знал, чем сейчас интересуется Принц. В последнее время свои нечастые выходные Принц проводил на разных курсах и тренингах. Вот только Дракон не был уверен, что Принцессе стоит об этом сказать.

Принц решил, что ему недостаёт некоторых знаний и навыков. Он определил, что в первую очередь хочет приобрести знания и навыки в 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