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