Shtirlitc

До сих пор идут споры, кто был прототипом разведчика Штирлица из книг Юлиана Семёнова и замечательного советского фильма «Семнадцать мгновений весны». Неясно также, почему Штирлиц стал героем множества анекдотов, сочетающих лаконичный стиль со словесной игрой.

Вы анализируете подборку анекдотов про Штирлица (N анекдотов) и выполнили P поисковых запросов. Вы вводили слово – поисковая система показывала вам количество анекдотов, содержащих заданное слово. Результаты зафиксированы. И теперь вам надо определить, каким может быть минимальное (М1) и максимальное (M2) количество анекдотов, не содержащих ни одного из искомых понятий, и минимальное (M3) и максимальное (M4) количество анекдотов, содержащих сразу все искомые понятия. Поскольку суть запросов для решения задачи не важна (известно, что все они состояли из одного слова и не повторялись), во входные данные включены только их результаты.

Входные данные: в первой строке натуральные числа N (не больше миллиона) и P (не больше 100). Далее следуют P строк с целыми числами – результаты поисковых запросов.

Выходные данные: четыре целых числа в одной строке через пробел, М1, М2, М3, М4.