Галактические Властелины
Правильная версия
Увидит ли галактика наконец мир? Все военачальники собрались, чтобы разделить всё пространство между собой. Переговоры зашли довольно далеко, и военачальники наконец согласились на мирный способ решения вопроса о том, кто что получит. Двумерная галактическая карта должна сначала быть разделена на сектора, разрезав её вдоль набора бесконечных линий. Военачальник с самым большим боевым флотом выберет один сектор, затем военачальник со вторым по величине флотом выберет другой сектор и так далее, пока все не получат сектор. Это повторяется до тех пор, пока не останется секторов.
Были предложены различные наборы линий, и вам предстоит представить эти альтернативы на встрече. Чтобы убедиться, что будет мир, вы готовы немного изменить предложения. У вас есть некоторый опыт с военачальниками, и вы знаете, что ни один военачальник не согласится на меньшее пространство, чем у других, поэтому для достижения мира все они должны получить точно такую же площадь на карте. Поскольку пространство бесконечно, карта тоже бесконечна. Некоторые сектора, следовательно, будут иметь бесконечную площадь, и именно такое количество пространства все захотят. Сколько дополнительных линий вам нужно будет добавить, чтобы каждый военачальник мог получить хотя бы один сектор с бесконечной площадью?
Входные данные
Первая строка входных данных содержит два положительных целых числа W и N, (1 ≤ W, N ≤ 100), обозначающих количество военачальников и количество линий в предложенном разделе пространства. Далее следуют N строк, каждая из которых содержит четыре целых числа x_1, y_1, x_2 и y_2, каждое из которых имеет абсолютное значение не более 10000. Это означает, что одна линия пересекает две точки (x_1, y_1) и (x_2, y_2) на галактической карте. Эти две точки не будут одинаковыми.
Выходные данные
Выведите количество линий, которые вам нужно будет добавить к этому предложению, чтобы удовлетворить всех военачальников.