Простая монотонность
Пусть есть некотороая булевая функция, определенная на некотором множестве булевых векторов размерности K. Один вектор является предшествующим по отношению к другому, если они различны и каждая координата первого вектора не больше чем соответствующая координата второго. Функция называется монотонной, если её значение на каждом векторе не меньше чем на любом предшествующем векторе. Требуется переопределить функцию в минимальном количестве векторов, чтобы она стала монотонной.
Входные данные
Два числа N и k (1 ≤ N ≤ 1000, 1 ≤ K ≤ 10) — количество векторов и размерность. Далее N строк по k+1 числу в каждой — булевый вектор и значение функции в нём. Все числа - 0 или 1. Все вектора различны.
Выходные данные
В первой строке минимальное количество векторов, значение функции в которых необходимо изменить, чтобы она стала монотонной. Во второй строке номера этих векторов без повторений в любом порядке.