eolymp
bolt
Try our new interface for solving problems
Problems

Простая монотонность

Простая монотонность

Time limit 1 second
Memory limit 256 MiB

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

Input data

Два числа N и k (1N1000, 1K10) — количество векторов и размерность. Далее N строк по k+1 числу в каждой — булевый вектор и значение функции в нём. Все числа - 0 или 1. Все вектора различны.

Output data

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

Examples

Input example #1
8 3
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0
Output example #1
2
1 8 
Source III International Summer School Programming in Sevastopol 2012