D. Загрузка файла
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В торрент-трекере качается файл, который раздают N сидеров. Файл поделён на M равных фрагментов. Для каждого сидера известно какие фрагменты у него доступны.

Чтобы скачать файл, нужно скачать все фрагменты. Канал скачивания имеет неограниченную скорость, фрагменты можно скачивать параллельно у нескольких сидеров. Тем не менее, скорость раздачи у сидеров ограничена: у i-го сидера на раздачу одного фрагмента уходит ti секунд. Сидер может раздавать одновременно только один фрагмент.

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

Входные данные

Первая строка содержит два целых числа N и M — количество сидеров и количество фрагментов (1 ≤ N, M ≤ 100).

В следующих N строках содержатся описания сидеров в виде строки ai и целого числа ti (1 ≤ ti ≤ 106). Строка ai содержит N символов и описывает фрагменты: доступные обозначаются символом «+», а недоступные «.».

Выходные данные

В первую строку выведите минимальное время, необходимое для загрузки всего файла.

Во второй строке выведите M целых чисел si, означающих, что для загрузки всего файла i-ю часть нужно скачивать у сидера с номером si (1 ≤ si ≤ N).

Если вариантов оптимальной загрузки несколько, можно вывести любой.

Примеры
Входные данные
3 4
.+.+ 1
+... 4
+.+. 3
Выходные данные
4
2 1 3 1
Входные данные
2 5
+++++ 2
+++++ 3
Выходные данные
6
1 2 1 2 1