Чемпионат КРОК 2012 - Финал |
---|
Закончено |
Зоопарк в Сеточном Королевстве представляет собой бесконечную сетку. В зоопарке есть n биноклей для наблюдения, расположенных на оси OX. Для каждого i от 1 до n включительно, существует ровно один бинокль, расположенный в точке с координатами (i, 0). В зоопарке есть m фламинго, расположенных в точках с положительными координатами. Сейчас фламинго спят и можно предположить, что они не двигаются.
Чтобы получше рассмотреть фламинго, любой бинокль может быть повернут на любой угол (не обязательно целый). После поворота с помощью бинокля можно увидеть всех фламинго, расположенных на прямой, проходящей через этот бинокль и направленной в сторону, в которую повернут бинокль. Другими словами, вы можете повернуть бинокль по направлению некоторой прямой, проходящей через этот бинокль, тогда с помощью бинокля можно будет увидеть всех фламинго, находящихся на этой прямой.
Сегодня несколько ребят из престижного садика Codeforces отправились в полевые исследования в зоопарк. Их учитель хотел бы повернуть каждый бинокль по направлению, при котором количество фламинго, которых можно увидеть в этот бинокль, максимально. Учителю интересна сумма этих значений по всем биноклям. Пожалуйста, помогите ему найти эту сумму.
Первая строка содержит два целых числа, записанных через пробел: n и m (1 ≤ n ≤ 106, 1 ≤ m ≤ 250) — количество биноклей и количество фламинго, соответственно.
Затем следуют m строк, на i-ой строке записаны через пробел два целых числа xi и yi (1 ≤ xi, yi ≤ 109), что означает, что i-ый фламинго находится в точке (xi, yi).
Все фламинго находятся в разных точках.
Выведите единственное целое число — наибольшее общее количество фламинго, которых можно увидеть во все бинокли.
5 5
2 1
4 1
3 2
4 3
4 4
11
Ответ на тест из примера проиллюстрирован ниже.
Название |
---|